题解：线性筛法求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]，累加所有数的约数个数。