CSP-S 2023 第一轮 第23题：当输入为“10”时，输出的第一行大于第二行。（）

题目

#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$ 的自然数，完成下面的判断题和单选题:

当输入为 10 时，输出的第一行大于第二行。（）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误），因为输入 10 时，两行输出都是 87。

这两个函数实际上都在计算：从 1 到 n，每个数的所有正因数之和，再累加。

对于 solve1，最后一个循环中的 f[i] 表示 i 的正因数之和。原因是：若 \(i=p^a m\)，其中 \(p\) 为 i 的最小质因子，且 \(m\) 不含因子 \(p\)，那么更新前 f[i]=p、g[i]=p^a，更新公式就是：

\[ f[i]=f[m]\frac{p^{a+1}-1}{p-1} =f[m](1+p+\cdots+p^a) \]

因此，1 到 10 的正因数之和依次为：

``text 1, 3, 4, 7, 6, 12, 8, 15, 13, 18 ``

相加得到 87。

对于 solve2，n / i 是整数除法，表示 1 到 n 中有多少个数是 i 的倍数。每个这样的数都有因数 i，所以因数 i 的总贡献是：

\[ i\left\lfloor\frac ni\right\rfloor \]

它只是换了一个统计顺序，结果同样是 87。

所以实际输出为：

``text 87 87 ``

第一行等于第二行，“第一行大于第二行”的说法错误。