CSP-S 2023 第一轮 第22题：将第15行删去，输出不变。（）

题目

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

将第 $15$ 行删去，输出不变。（）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F，错误。 第 15 行是：

``cpp reverse(d.begin(), d.end()); ``

它让质数 i 的各次幂从大到小处理，使 g[j] 记录能整除 j 的最大的 i 的幂。一旦 p[j] 被设为 false，后续就不能修改 g[j]，所以处理顺序很重要。

以 n = 4 为反例，此时 i = 2：

• 保留第 15 行：d = {4, 2}，先得到 g[4] = 4，最终

\[ f[4]=f[1]\times\frac{4\times2-1}{2-1}=7. \]

• 删去第 15 行：d = {2, 4}，先得到 g[4] = 2，同时 p[4] = false，之后无法更新。最终

\[ f[4]=f[2]\times\frac{2\times2-1}{2-1}=3\times3=9. \]

因此，原程序输出： ``text 15 15 ``

删去后输出： ``text 17 15 ``

输出发生变化，所以判断为 错误。