BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 20 题

（2）给定正整数 $n$，请编写程序计算它的全部正约数之和。输入数据保证 $n \leq 10\ 000\ 000$。

试用最优选项补全程序。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int n, d[MAXN];
bool flag[MAXN];

long long value(int x, int k) {
    long long ans = 1;
    for (int i = 1; i <= k + 1; i++)
        ans *= x;
    return ___①___;
}

int main() {
    for (___②___) {
        if (flag[i]) continue;
        for (int j = i; j < MAXN; j += i) {
            if (flag[j]) continue;
            flag[j] = true;
            ___③___;
        }
    }

    cin >> n;
    long long ans = 1;
    int last = -1, t = 0;
    for (; n > 1; ___④___) {
        if (d[n] == last) t++;
        else {
            ans *= value(last, t);
            ___⑤___;
        }
    }
    ans *= value(last, t);
    cout << ans << endl;
    return 0;
}

1. ① 处应填（ ）。 A. ans / (x - 1) B. ans * (x - 1) C. `(ans -

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

这题就是考质因数分解求约数和。核心思路是先用埃氏筛法把每个数的最小质因子存进 d[]，然后不断用 d[n] 把 n 除尽，统计每个质因子的次数，最后用等比数列求和公式算贡献乘起来即可。

最容易栽跟头的是把筛法逻辑搞反：d[j] 应该存的是 j 的最小质因子 i，而不是反过来存 d[i]=j；还有很多人看到 n>1 就以为要一直减 1 或减 d[n]，其实必须用除法 n/=d[n] 才能把质因子清零；求和公式里 ans 初始是 1，循环里乘 (p^(t+1)-1)/(p-1)，很多人会漏掉分子减 1 或者分母除错；最后别忘了循环结束后再乘一次当前质因子的贡献。

这道题考查的是数论中约数和的计算，结合了筛法预处理和质因数分解。题目给定 n≤10000000，要求输出所有正约数之和。如果直接枚举 1 到 n 求和，复杂度是 O(n)，在数据范围内勉强能过，但题目显然希望我们使用更优的算法，即质因数分解后利用约数和公式。

首先回顾一下核心概念。算术基本定理告诉我们，任何一个大于 1 的整数 n 都可以唯一地分解为质数的乘积：n = p1^a1 * p2^a2 * ... * pk^ak。那么 n 的所有正约数之和 σ(n) 就等于 (p1^0 + p1^1 + ... + p1^a1) * (p2^0 + p2^1 + ... + p2^a2) * ... * (pk^0 + pk^1 + ... + pk^ak)。这是一个非常经典的等比数列求和公式，每一项是 (p^(a+1)-1)/(p-1)。

接下来看命题人的挖坑点。这道题没有直接让你分解 n，而是给了一个巨大的数组 d[MAXN] 和一个筛法过程。这明显是在暗示我们要用线性筛或者埃氏筛的变种来预处理每个数的最小质因子。为什么是最小质因子？因为当我们对 n 进行分解时，如果我们每次取出最小质因子 p，那么 n/p 一定比 n 小，而且 p 肯定是 n 的质因子。如果我们能预先知道每个数的最小质因子，分解过程就极其高效：不断用 d[n] 除 n，直到 n 变为 1。如果 d[n] 存的是错误的值（比如存的是合数，或者存的是其他无关值），分解就会陷入死循环或者算错。

现在逐空分析代码。

先看 value 函数，它的作用是计算等比数列的和。参数 x 是质因子，k 是次数。循环里 ans *= x，执行了 k+1 次，所以 ans 最终等于 x^(k+1)。题目要求的是 (x^(k+1)-1)/(x-1)。观察选项，A 是除以 x-1，正好得到 (x^(k+1)-1)/(x-1)。这里有个细节，很多人可能会想是不是要乘 (x-1) 或者减 1，但 ans 已经是 x^(k+1) 了，只需要减去 1 再除以 x-1 即可。所以①处填 A。

再看筛法部分。for 循环从②开始，里面判断 if(flag[i]) continue; 说明 flag 数组用来标记合数。经典的埃氏筛是从 2 开始遍历，因为 1 既不是质数也不是合数，而且如果从 1 开始，flag[1] 初始是 false，进入循环后会把所有数都标记为合数，逻辑就乱了。所以②必须从 2 开始，即 int i = 2; i < MAXN; i++。这里要注意 MAXN 的定义是 1000005，所以 i < MAXN 是安全的，不会越界访问 d[MAXN]。如果选 B 或 D 从 1 开始，逻辑全崩；选 C 虽然从 2 开始，但 i < MAXN 在 i=MAXN-1 时还会执行一次，虽然无害，但通常习惯写成 i <= MAXN 或者 i < MAXN 配合循环条件，不过这里关键是起始值必须是 2。综合来看，C 是最符合逻辑的写法。

接着看内层循环，j 从 i 开始，步长为 i，这是标准的埃氏筛标记倍数的做法。当 flag[j] 为 false 时，说明 j 是第一次被访问，此时 j 一定是 i 的倍数且 i 是最小的质因子（因为从小到大遍历）。这时候我们需要把 d[j] 记录下来，d[j] 应该存的是 j 的最小质因子，也就是当前的 i。所以③处填 A：d[j] = i。很多人会混淆，觉得 d[i] 应该存 i 自己，或者 d[j] 存 j，这都是错的，d 数组的作用就是记录最小质因子，用来后续分解。

然后进入主逻辑，输入 n 后，代码开始分解。last 记录当前质因子，t 记录次数。循环条件 n > 1，④处需要更新 n。因为我们已经知道 d[n] 是 n 的最小质因子，为了彻底分解，必须用除法：n /= d[n]。如果用减法 n -= d[n]，n 会变成一个奇怪的数，d[n] 可能根本不存在或者不是质因子，导致死循环或错误。所以④填 C。

在循环内部，如果 d[n] 等于 last，说明是同一个质因子，次数 t 加 1；否则，说明遇到了新的质因子，需要把刚才那个质因子的贡献乘进去。贡献就是 value(last, t)，然后更新 last = d[n]，t 重置。注意 t 重置应该是 t = 0 还是 t = 1？这里要看逻辑：当遇到新质因子时，我们刚进入 else 分支，此时还没有统计这个新质因子的次数，所以 t 应该从 0 开始计数。但是，代码在循环结束后还有一行 ans *= value(last, t)，这意味着循环结束时，last 是最后一个质因子，t 是它的次数。如果在循环里遇到新质因子时把 t 设为 1，那么循环结束时 t 已经是 1 了，再乘一次 value(last, 1) 就多乘了一次。正确的做法是，在循环里遇到新质因子时，先乘掉上一个的贡献，然后更新 last 为新质因子，t 设为 0，让它在循环里自增。但是看代码结构，else 分支里先乘了上一个，然后更新 last 和 t。如果 t 设为 0，那么循环里第一次遇到这个新质因子时，d[n] == last 成立，t 会变成 1，这是对的。但是循环结束后，还会执行一次 ans *= value(last, t)，这时候 t 是 1，相当于多乘了一次。等等，这里有个陷阱。实际上，代码的逻辑是：循环里只要 d[n] != last，就说明上一个质因子已经结束，乘进去，然后更新 last 和 t。如果 t 设为 0，那么循环里第一次遇到这个新质因子时，d[n] == last 成立，t 自增为 1，这是对的。但是循环结束后，还会执行一次 ans *= value(last, t)，这时候 t 是 1，相当于多乘了一次。这说明 t 在更新时应该设为 1，这样循环结束后 t 是 1，再乘一次 value(last, 1) 就是对的。让我们重新梳理：假设 n = 12 = 2^2 * 3。初始 last = -1, t = 0。n=12, d[12]=2, d[12]!=last, 乘 value(-1,0)=1, last=2, t=1。n=6, d[6]=2, d[6]==last, t=2。n=3, d[3]=3, d[3]!=last, 乘 value(2,2)=7, last=3, t=1。n=1, 循环结束。最后 ans *= value(3,1)=4。总乘积 1*7*4=28。正确。所以⑤处填 B：last = d[n], t = 1。

最后，整个算法的时间复杂度主要由筛法决定，筛法是 O(MAXN log log MAXN)，分解是 O(log n)，总复杂度在 10^7 范围内完全可接受。空间复杂度 O(MAXN) 也是合理的。

总结一下，这道题的关键在于理解埃氏筛的变种：d[j] 存最小质因子，而不是存 j 本身；分解时用除法；求和公式的细节；以及循环结束时多乘一次的处理。只要把这些点都抓住，就能避开所有坑。