线性筛：约数个数与约数之和预处理

在使用线性筛（欧拉筛）时，我们可以利用积性函数的性质，在 $O(n)$ 的时间内预处理出每个数的约数个数和约数之和。

1. 数组含义详细解析

假设一个数 $i$ 的质因数分解式为：$i = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$，其中 $p_1$ 是 $i$ 的最小质因子。

2. 核心数学原理

线性筛的核心在于 i % k == 0 的判断，这决定了新合成的数 $i \times k$ 的最小质因子状态：

1. 若 i % k != 0：说明 $k$ 是 $i \times k$ 的最小质因子，且与 $i$ 互质。

   • 根据积性函数性质：$f[i \times k] = f[i] \times f[k]$，由于 $k$ 是质数，$f[k]=2$。
   • 同理：$g[i \times k] = g[i] \times g[k] = g[i] \times (k+1)$。
   • 此时 $i$ 整体成为了 $i \times k$ 除去最小质因子后的部分，故 d[i*k] = g[i]。

2. 若 i % k == 0：说明 $k$ 是 $i$ 的最小质因子。

   • 约数个数：$i \times k$ 的最小质因子幂次从 $e_1$ 变为 $e_1+1$。原贡献项从 $(e_1+1)$ 变为 $(e_1+2)$。
   • 约数之和：设 $i = k^{e_1} \cdot T$，则 $g[i] = (1+k+\dots+k^{e_1}) \cdot g[T]$。新和 $g[i \cdot k] = g[i] \cdot k + g[T]$。这里的 $g[T]$ 就是代码中的 d[i]。

3. C++ 代码实现（带详细注释）

#include <iostream>
using namespace std;

const int n = 100000;
const int N = n + 1;

int m; // 质数计数器
int a[N]; // 合数标记数组
int b[N]; // 质数表
int c[N]; // 最小质因子的指数 e1
int d[N]; // 除去最小质因子部分后的约数之和 sigma(T)
int f[N]; // 约数个数 d(n)
int g[N]; // 约数之和 sigma(n)

void init()
{
    f[1] = g[1] = 1; // 1 的特殊处理
    for (int i = 2; i <= n; i++){
        if (!a[i]){ // i 是质数
            b[m++] = i;
            c[i] = 1;     // 质数 p 的最小质因子指数是 1
            f[i] = 2;     // 质数约数只有 1 和 p
            d[i] = 1;     // sigma(i/p^1) = sigma(1) = 1
            g[i] = i + 1; // sigma(p) = 1 + p
        }
        for (int j = 0; j < m && b[j] * i <= n; j++)
        {
            int k = b[j]; // k 是当前最小质因子
            a[i * k] = 1; // 标记合数

            if (i % k == 0){ // k 已经是 i 的最小质因子
                // 更新最小质因子指数
                c[i * k] = c[i] + 1; 
                // 约数个数：f(i*k) = f(i) / (e1 + 1) * (e1 + 2)
                f[i * k] = f[i] / (c[i] + 1) * (c[i * k] + 1);

                // 约数之和递推公式
                d[i * k] = d[i]; 
                g[i * k] = g[i] * k + d[i];

                break; // 线性筛关键：每个数只被其最小质因子筛掉
            }
            else { // k 小于 i 的最小质因子
                c[i * k] = 1; // k 成为新的最小质因子，指数为 1
                f[i * k] = f[i] * 2; // 积性函数性质 f(i*k) = f(i) * f(k)

                d[i * k] = g[i]; // 除去最小质因子 k 后，剩下的部分是 i
                g[i * k] = g[i] * (k + 1); // 积性函数性质 g(i*k) = g(i) * g(k)
            }
        }
    }
}

int main()
{
    init();

    int x;
    if(cin >> x) {
        // 输出 x 的约数个数和约数之和
        cout << f[x] << " " << g[x] << endl;
    }
    return 0;
}

以下是针对该线性筛程序相关问题的详细解析与答案：

题目解析与答案

1）若输入不为“1”，把第 13 行删去 不会 影响输出的结果。（ ）

• 答案：A. 对
• 解析： 第 13 行代码是 f[1] = g[1] = 1;。在 init() 函数的循环中，i 是从 2 开始的。线性筛中所有合数的状态都是由质数（种子）递推而来的。对于任何 $i \ge 2$，其约数个数和约数之和的计算并不依赖于 $f[1]$ 或 $g[1]$ 的值。因此，只要输入 $x \neq 1$，删掉这一行对结果没有影响。

2）第 25 行的“f[i] / (c[i] + 1)”可能存在无法整除而向下取整的情况。（ ）

• 答案：B. 错
• 解析： 根据约数个数公式 $f(i) = (e_1+1)(e_2+1)\dots(e_k+1)$，其中 $c[i]$ 存储的就是最小质因子的指数 $e_1$。因此，$(c[i]+1)$ 必然是 $f[i]$ 的一个约数，除法操作永远可以整除，不会出现精度丢失。

3）在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。（ ）

• 答案：B. 错
• 解析：
  • f 数组（约数个数）显然不单调，例如 $f[3]=2, f[4]=3, f[5]=2$。
  • g 数组（约数之和）也不单调。例如：
    • $g[4] = 1+2+4 = 7$
    • $g[5] = 1+5 = 6$
  • 因为 $g[5] < g[4]$，所以 g 数组也不是单调递增的。

4）init 函数的时间复杂度为（ ）。

• 答案：A. $O(n)$
• 解析： 该算法为标准的欧拉筛（线性筛）。通过 if (i % k == 0) break; 这一语句，保证了每个合数只会被其最小的质因子筛掉一次，因此每个数只被访问常数次，总时间复杂度为 $O(n)$。

5）在执行完 init() 后，f[1], f[2], f[3] …… f[100] 中有（ ）个等于 2。

• 答案：C. 25
• 解析： $f[x] = 2$ 表示 $x$ 恰好有两个正约数（1 和 它本身），即 $x$ 是质数。 问题转化为求 $1 \sim 100$ 以内的质数个数。根据常识或计数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97，共 25 个。

6）当输入为 “1000” 时，输出为（ ）。

• 答案：C. “16 2340”
• 解析： 对 $1000$ 进行质因数分解：$1000 = 10^3 = (2 \times 5)^3 = 2^3 \times 5^3$。
  • 约数个数 $f[1000]$：$(3+1) \times (3+1) = 16$。
  • 约数之和 $g[1000]$： $g[1000] = (2^0+2^1+2^2+2^3) \times (5^0+5^1+5^2+5^3)$ $g[1000] = (1+2+4+8) \times (1+5+25+125)$ $g[1000] = 15 \times 156 = 2340$。
  • 因此输出为 16 2340。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com