题解：线性筛法求1~n的约数个数之和

一、欧拉筛的核心原理

欧拉筛（线性筛） 是一种高效的质数筛选算法，核心思想是 每个合数仅被其最小质因子筛除一次。

• 为什么用欧拉筛：
  1. 时间复杂度最优：传统埃氏筛的时间复杂度为 $O(n \log \log n)$，而欧拉筛为 $O(n)$，适合处理大规模数据（如 $n=10^7$）。
  2. 记录关键信息：在筛质数的同时，可以记录每个数的最小质因子及其幂次，为后续计算约数个数提供数据支持。

二、为什么用欧拉筛求约数个数

约数个数公式：

其中 $e_i$是质因数分解中各质数的指数。
欧拉筛的优势：

1. 动态维护最小质因子：通过记录每个数的最小质因子幂次 num[i]，可以在筛的过程中直接更新约数个数 d[i]。
2. 避免重复计算：每个合数仅被处理一次，保证时间复杂度为 $O(n)$。

三、代码详细解释

#include<bits/stdc++.h>
using namespace std;

int n;
vector<bool> isPrime(1000100, true);  // 质数标记数组
vector<int> d(1000100, 1);           // 约数个数数组
vector<int> num(1000100, 0);         // 最小质因子幂次数组

int countDivisors() {
    isPrime[0] = isPrime[1] = false;  // 0和1不是质数
    d[1] = 1;                         // 1的约数个数为1
    vector<int> primes;               // 存储质数列表

    for (int i = 2; i <= n; i++) {    // 从2开始遍历每个数
        if (isPrime[i]) {             // 如果i是质数
            primes.push_back(i);      // 加入质数列表
            d[i] = 2;                 // 质数的约数个数为2（1和自身）
            num[i] = 1;               // 质数的最小质因子幂次为1
        }
        // 用当前质数p筛去i*p
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;  // 标记合数
            if (i % primes[j] == 0) {        // primes[j]是i的最小质因子
                num[i * primes[j]] = num[i] + 1;  // 幂次+1
                // 动态调整约数个数：d[i*p] = d[i]/(e+1) * (e+2)
                d[i * primes[j]] = d[i] / (num[i] + 1) * (num[i * primes[j]] + 1);
                break;  // 关键：确保每个合数只被筛一次
            } else {  // primes[j]是i*p的最小质因子
                num[i * primes[j]] = 1;      // 新质因子，幂次为1
                d[i * primes[j]] = d[i] * d[primes[j]];  // 约数个数相乘
            }
        }
    }
    // 累加所有数的约数个数
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += d[i];
    return ans;
}

int main() {
    cin >> n;
    cout << countDivisors();
    return 0;
}

四、关键步骤解析

1. 初始化：

   • isPrime 标记所有数为质数，后续逐步筛除合数。
   • d[1] = 1：显式设置1的约数个数。

2. 质数处理：

   • 当 i 是质数时，加入质数列表 primes，并初始化 d[i] = 2（质数的约数个数为2）。

3. 合数筛除与约数计算：

   • 内层循环：遍历质数表，筛去 i * primes[j]。
   • 整除判断：
     • 若 i % primes[j] == 0，说明 primes[j] 是 i 的最小质因子。
       • 更新 num[i*p] 为 num[i]+1（幂次增加）。
       • 动态调整 d[i*p]
     • 否则，primes[j] 是 i*p 的最小质因子，直接相乘约数个数。

4. 结果累加：

   • 遍历 d[1..n]，累加所有数的约数个数。

数学原理详解

本题要求计算和式 $\sum_{i=1}^n f(i)$， 其中 $f(i)$ 表示正整数 $i$ 的约数个数。直接对每个 $i$ 计算约数个数再求和的方法时间复杂度为 $O(n \sqrt{n})$，当 $n$ 较大时（如 $n \leq 10^6$）效率较低。因此，我们需要一种更高效的数学方法。

关键变换：交换求和顺序

考虑所有从 $1$ 到 $n$ 的整数，每个数 $i$ 的约数个数 $f(i)$ 可以理解为所有能整除 $i$ 的约数 $k$ 的个数。

因此，原和式可以重写为：

$\sum_{i=1}^n f(i)$ = $\sum_{i=1}^n \sum_{k \mid i} 1$

$k \mid i$ 就是k ​​整除​​ i

这里内层求和表示对每个 $i$，计算其约数的个数。现在，我们交换求和顺序：改为先固定约数 $k$，然后计算 $k$ 作为约数出现在多少个 $i$ 中（其中 $i \leq n$）。由于 $k$ 是 $i$ 的约数当且仅当 $i$ 是 $k$ 的倍数，因此对于每个 $k$，满足 $k \mid i$ 且 $i \leq n$ 的 $i$ 的个数就是 $k$ 的倍数中不超过 $n$ 的个数，即 $\left\lfloor \frac{n}{k} \right\rfloor$。

换句话说：

-$\left\lfloor \frac{n}{k} \right\rfloor$ 正是$k$ 在范围$1$ 到$n$ 中作为约数出现的次数（即“有效的个数”）。例如，如果$k=2$ 和$n=5$，那么$2$ 的倍数有$2, 4$，所以出现了 2 次，而$\left\lfloor \frac{5}{2} \right\rfloor = 2$。

因此，求和$\sum_{k=1}^n$$\left\lfloor \frac{n}{k} \right\rfloor$ 实际上是在对所有可能的约数$k$ 计算其出现的频次，从而等价于原问题。这种变换是数论中常见的技巧，称为“除数求和”或“交换求和顺序”。

因此，原和式等价于：

$\sum_{i=1}^n f(i)$= $\sum_{k=1}^n$$\left\lfloor \frac{n}{k} \right\rfloor$

这个变换将问题转化为计算所有 $k$ 从 $1$ 到 $n$ 的 $\left\lfloor \frac{n}{k} \right\rfloor$ 之和。

效率分析

直接计算新和式的时间复杂度为 $O(n)$，对于 $n \leq 10^6$ 是可行的。但还可以进一步优化：由于 $\left\lfloor \frac{n}{k} \right\rfloor$ 的值对于连续的 $k$ 可能相同，我们可以找到使值相同的区间，批量计算。具体来说，对于每个 $k$，存在最大的 $m$ 使得

$\left\lfloor \frac{n}{k} \right\rfloor$ =$\left\lfloor \frac{n}{m} \right\rfloor$，则 $m=⌊\frac{n}{⌊n /k⌋}⌋$。

这样，求和的时间复杂度可降为 $O(\sqrt{n})$。但对于本题范围，直接循环 $k$ 从 $1$ 到 $n$ 也已足够。

样例验证

取输入样例 $n = 3$：

• 直接计算：
• $f(1) = 1$，$f(2) = 2$，$f(3) = 2$，
• 和为 $1 + 2 + 2 = 5$。
• 用新方法：
• $\left\lfloor \frac{3}{1} \right\rfloor = 3$，$\left\lfloor \frac{3}{2} \right\rfloor = 1$，$\left\lfloor \frac{3}{3} \right\rfloor = 1$，
• 和为 $3 + 1 + 1 = 5$。结果一致。