CSP-S 2023 第一轮 第24题：（2分）当输入为“1000”时，输出的第一行与第二行相等。（

题目

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

long long solve1(int n) {
    vector<bool> p(n + 1, true);
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            for (int k = i; k <= n; k *= i) d.push_back(k);
            reverse(d.begin(), d.end());
            for (int k : d) {
                for (int j = k; j <= n; j += k) {
                    if (p[j]) {
                        p[j] = false;
                        f[j] = i;
                        g[j] = k;
                    }
                }
            }
        }
    }
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
        sum += f[i];
    }
    return sum;
}

long long solve2(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << solve1(n) << endl;
    cout << solve2(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 $1000000$ 的自然数，完成下面的判断题和单选题:

（2 分） 当输入为 1000 时，输出的第一行与第二行相等。（）

选项

• T. 正确
• F. 错误

答案

T

题解

选 T，正确。 两个函数算的都是“从 \(1\) 到 \(n\) 的所有整数的正因数之和”。

看 solve1：在筛选结束后，对于每个 \(i\ge2\)：

• f[i] 存的是 \(i\) 的最小质因数 \(p\)；
• g[i] 存的是 \(i\) 中包含的最高次 \(p\) 的幂 \(p^a\)。

令 \(i=m p^a\)，其中 \(m\) 不再含质因数 \(p\)。最后的递推式相当于： \[ f[i]=f[m]\cdot\frac{p^{a+1}-1}{p-1} =f[m](1+p+\cdots+p^a). \] 这正是正因数和的计算公式。因此 solve1(n) 求出的是 \(1\) 到 \(n\) 每个数的正因数和，再累加。

看 solve2：它换了一个统计角度。对于因数 \(i\)，\(1\) 到 \(n\) 中有 \[ \left\lfloor\frac ni\right\rfloor \] 个数是它的倍数，所以它对总和的贡献为 \[ i\left\lfloor\frac ni\right\rfloor. \] 把所有 \(i\) 的贡献相加，得到的也是上述总和。

所以输入 1000 时，两行输出相等。