CSP-S 2023 第一轮 第26题：solve2(n）的时间复杂度为（

题目

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

solve2(n) 的时间复杂度为（）。

选项

• A. $O(n^2)$
• B. $O(n)$
• C. $O(n \log n)$
• D. $O(n \sqrt n)$

答案

B

题解

选 B．\(O(n)\)。

只看 solve2(n)：

``cpp for (int i = 1; i <= n; i++) { sum += i * (n / i); } ``

• i 从 \(1\) 到 \(n\)，循环共执行 \(n\) 次。
• 每次循环只进行固定次数的除法、乘法和加法，耗时为 \(O(1)\)。

因此总时间复杂度为： \[ n \times O(1) = \boxed{O(n)} \]

注意：n / i 是一次整数除法运算，并不表示要循环 \(n/i\) 次；solve1 的代码也不影响 solve2 的复杂度。