CSP-J 入门级 · CSP 2021 入门级第一轮 第 18 题

（3）

#include <iostream>
using namespace std;

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

int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];

void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}

int main()

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题是线性筛法的经典应用，核心在于利用积性函数的性质，在筛出质数时同步计算约数个数和约数之和。拿到题先别急着看代码，脑子里过一遍欧拉筛的逻辑：每个合数只被它的最小质因子筛掉一次。然后顺着这个逻辑，去推导f和g的递推公式，再代入具体数值验证。

最容易掉进的坑有两个：一是误以为f数组是单调递增的，其实质数的f值是2，紧接着的合数f值会变大，中间穿插着f值较小的数，整体震荡；二是看到除法操作就慌，觉得可能除不尽，其实由积性函数的定义，f[i]一定能被c[i*k]整除。还有一个细节，第13行给质数初始化d[i]=1，这行看起来多余，因为后面循环里i%k==0的情况会覆盖它，删了也不影响结果，很多学生会被这种‘无用代码’迷惑。

考察知识点：数论 — 线性筛（欧拉筛）+ 积性函数（约数个数函数 d(n) 与约数之和函数 σ(n)）。

核心概念：

• f[i] 存储的是 i 的约数个数，记作 d(i)。
• g[i] 存储的是 i 的约数之和，记作 σ(i)。
• c[i] 记录 i 的最小质因子的指数（即 i 中包含该质因子的最高次幂）。
• d[i] 是一个辅助变量，用于快速计算约数之和。

命题视角：命题人喜欢把线性筛和积性函数结合考，因为单纯考筛法太基础，单纯考积性函数推导容易卡壳，两者结合既考算法实现又考数学推导。挖坑点在于：1. 让学生判断代码中看似多余的操作是否影响结果；2. 利用数学性质判断除法是否溢出或取整；3. 通过观察数组单调性来考察对函数增长趋势的理解。

思考心法：拿到这种题，第一步是识别出这是线性筛，因为外层循环 i 从 2 到 n，内层用 b[j]（质数表）去筛合数，且 break 保证了每个合数只被最小质因子筛一次。第二步是明确 f 和 g 的积性：d(n) 和 σ(n) 都是积性函数，所以只要知道质数上的值和递推关系，就能算出所有数。第三步是推导递推式：

设 n = i × k，其中 k 是质数。

1. 若 i % k ≠ 0（k 是 i 的新质因子）： - 此时 i 和 k 互质。根据积性函数定义： - f[i*k] = f[i] * f[k]。因为 k 是质数，f[k]=2，所以 f[i*k] = f[i] * 2。 - g[i*k] = g[i] * g[k]。质数 k 的约数和是 1 + k，所以 g[i*k] = g[i] * (k + 1)。 - 同时更新辅助量：c[i*k] = 1（k 的指数为 1），d[i*k] = g[i]（因为 g[k]=k+1，d[i*k] 用来存 g[i]/g[k] 部分，即约数和去掉 k 因子后的部分）。

2. 若 i % k == 0（k 已在 i 中）： - 设 i 中 k 的指数为 c[i]，即 i = k^c * m，其中 m 与 k 互质。 - 那么 i*k 中 k 的指数变为 c[i]+1。 - 约数个数：f[i*k] = f[i] * (c[i]+2) / (c[i]+1)。因为约数个数公式是各质因子指数加 1 的乘积，增加一个指数相当于乘以 (c+2)/(c+1)。 - 约数之和：g[i*k] = g[i] * k + d[i]。这里 d[i] 实际上存的是 g[m]，即去掉 k 因子后的约数和。所以 g[i*k] = g[m] * k^c * (k+1) + g[m] * k = g[i] * k + d[i]。 - 辅助量更新：c[i*k] = c[i] + 1，d[i*k] = d[i]（因为 d[i*k] 应该存 g[m]，而 d[i] 就是 g[m]）。

逐题推演：

28. 删除第 13 行是否影响结果？ 第 13 行是 d[i] = 1, g[i] = i + 1;，这是给质数初始化 d 和 g。观察代码逻辑，当处理质数 i 时，内层循环 j=0，k=b[0]=2。如果 i=2，i%k=0，走第一个分支，会执行 d[i*k] = d[i]，此时 d[4] 会用到 d[2]。但注意，对于质数 i 本身，d[i] 的值在后续计算中只会在 i 作为‘被筛数’（即作为 i 的角色）时用到。然而，线性筛中，每个合数只被它的最小质因子筛掉。对于质数 i，它永远不会作为‘k’去筛其他数（因为 k 必须是 b[j]，而 b[j] 是质数表，i 作为质数会被放入 b 表，但此时 i 已经处理完了）。更关键的是，d[i] 在 i 是质数时，只在计算 i 的倍数时用到。如果 i 是质数，它的倍数 i*k 中，k 肯定是比 i 小的质数（因为 k 来自 b 表，且 i*k <= n，k 是 i 的因子）。等等，这里逻辑要理清楚：当处理质数 i 时，我们实际上是在初始化 f[i], g[i], c[i], d[i]。然后进入内层循环，用 b[j] 去筛 i 的倍数。如果 i 是质数，那么 i 本身不会被任何 b[j] 筛到（因为 b[j] 是质数，i 是质数，i*b[j] > i，除非 b[j]=1 但不存在）。所以 d[i] 的值只在 i 作为‘被筛数’时用到，但 i 是质数，它不会被筛。因此 d[i] 的初始化对于后续计算没有任何影响，删了完全没问题。答案选 A。

**29. f[i] / c[i*k] 是否可能除不尽？** 由上面的推导，f[i*k] = f[i] * (c[i]+2) / (c[i]+1)。这里 c[i*k] = c[i] + 1。所以 f[i] / c[i*k] 实际上是 f[i] / (c[i]+1)。而 f[i] 本身是 i 的约数个数，i 中 k 的指数是 c[i]，所以 i 的约数个数包含因子 (c[i]+1)。因此 f[i] 一定能被 c[i]+1 整除。代码中不会出现向下取整。答案选 B。

30. f 和 g 是否单调？ f[1]=1，f[2]=2，f[3]=2，f[4]=3，f[5]=2，f[6]=4... 显然 f 不是单调递增。g[1]=1，g[2]=3，g[3]=4，g[4]=7，g[5]=6，g[6]=12... g 也不是单调递增。答案选 B。

31. 时间复杂度？ 线性筛的核心性质是每个合数只被它的最小质因子筛一次，因此内层循环的总次数是 O(n)。答案选 A。

32. f[x]=2 的个数？ f[x]=2 当且仅当 x 是质数。1 到 100 中，质数有 2, 3, 5, ..., 97，共 25 个。答案选 C。

33. x=1000 的输出？ 我们需要计算 f[1000] 和 g[1000]。1000 = 2^3 * 5^3。f[1000] = (3+1)*(3+1) = 16。g[1000] = (2^4 - 1)/(2-1) * (5^4 - 1)/(5-1) = 15 * 156 = 2340。输出是 16 2340。答案选 C。

总结：这道题考察的是对线性筛法的深刻理解，以及积性函数的性质。解题的关键在于不要死记代码，而是从数学原理出发，推导出递推关系，然后用具体的例子验证。对于判断题，要细心观察代码执行流程，特别是质数初始化的部分是否真的被后续计算依赖。