CSP-S 2023 第一轮 第25题：solve1（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$ 的自然数，完成下面的判断题和单选题:

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

选项

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

答案

D

题解

选 D：\(O(n\log\log n)\)。关键是：外层的 if (p[i]) 使得只有质数 \(i\) 才会进入里面的循环，因此要按筛法分析，不能直接把每层循环的最大次数相乘。

1. 固定一个质数 \(i\)，内层循环执行多少次？

d 中存的是不超过 \(n\) 的 \(i\) 的幂：

\[ i,\ i^2,\ i^3,\ldots \]

reverse 只改变遍历顺序，不影响次数。

对于每个 \(k=i^a\)，循环

``cpp for (int j = k; j <= n; j += k) ``

执行 \(\lfloor n/i^a\rfloor\) 次。因此，这个质数对应的总次数为

\[ \left\lfloor\frac ni\right\rfloor+ \left\lfloor\frac n{i^2}\right\rfloor+\cdots \le n\left(\frac1i+\frac1{i^2}+\cdots\right) =\frac{n}{i-1}. \]

因为第一项就有 \(\lfloor n/i\rfloor\) 次，所以总次数是 \(\Theta(n/i)\)。

2. 对所有参与筛选的质数求和

只有 \(i\le\sqrt n\) 的质数参与筛选，因此总工作量为

\[ \Theta\left(n\sum_{\substack{i\le\sqrt n\\i\text{ 为质数}}}\frac1i\right). \]

利用筛法分析中的经典结论：

\[ \sum_{\substack{p\le x\\p\text{ 为质数}}}\frac1p =\Theta(\log\log x), \]

得到筛选部分的时间复杂度为

\[ \Theta(n\log\log n). \]

创建和反转 d 的开销也被上述工作量覆盖：每个存入 d 的 \(k\)，至少对应一次 j 循环。

3. 其余部分

数组初始化、后面的两个单层循环均为 \(O(n)\)，所以最终为

\[ \boxed{\Theta(n\log\log n)} \]

对应 D。

注意：虽然 p[j] = false 对每个数最多执行一次，但 if (p[j]) 仍然会被反复检查，所以不能据此判断为 \(O(n)\)。