CSP-J 2021 第一轮 第 31 题：程序（三）：init函数的时间复杂度

题目

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

#include <iostream>
using namespace std;

const int n = 100000;
const int N = n + 1;

int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];

void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}

int main()
{
    init();

    int x;
    cin >> x;
    cout << f[x] << ' ' << g[x] << endl;
    return 0;
}

init 函数的时间复杂度为（ ）。

选项

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

答案

A

题解

答案是 A. \(O(n)\)。这段代码使用的是线性筛（欧拉筛），关键在于内层循环中的 break。

虽然有两层循环，但内层循环的总执行次数并不是 \(n^2\)。我们看它每次处理的数： ``cpp int k = b[j]; a[i * k] = 1; ` 其中，b 按从小到大的顺序存放质数。当 k 是 i 的最小质因子时，i % k == 0，执行完本次操作就 break。因此，内层循环中使用的 k 不会超过 i` 的最小质因子。

这意味着：**每次生成的合数 i * k，其最小质因子一定是 k。**

对于任意合数 \(x\)，它的最小质因子 \(p\) 是唯一的，所以它只会在 \[ k=p,\qquad i=\frac{x}{p} \] 时被处理一次。

例如 \(12\)：

• 会通过 \(6\times2\) 被处理；
• 不会通过 \(4\times3\) 被重复处理，因为 i = 4 时，循环在 k = 2 处就结束了。

因此，内层循环总共只处理了 \(n\) 以内的每个合数一次，总工作量为 \(O(n)\)；外层循环也是 \(O(n)\)。循环中的其他操作都是常数时间，所以：

\[ \boxed{T(n)=O(n)} \]

这题的要点是：嵌套循环不一定是平方复杂度，要统计内层循环的总执行次数。