共48道题，当前是第47题

初赛真题

01 #include <cmath>
02 #include <cstring>
03 #include <iostream>
04 
05 const int MAXN = 1000000;
06 int n;
07 int f1[MAXN], f2[MAXN], f3[MAXN];
08 
09 int calc_f1(int x) {
10     int ans = 1;
11     int maxNum = sqrt(x);
12     for (int i = 2; i <= maxNum; ++i)
13         if (x % i == 0) {
14             ans = -ans;
15             x /= i;
16             if (x % i == 0)
17                 return 0;
18         }
19     if (x != 1)
20         ans = -ans;
21     return ans;
22 }
23 
24 int calc_f2(int x) {
25     return x;
26 }
27 
28 void convolute() {
29     memset(f3, 0, sizeof(f3));
30     for (int i = 1; i <= n; ++i)
31         for (int j = 1; j <= n / i; ++j)
32             if (i * j <= n)
33                 f3[i * j] = f3[i * j] + f1[i] * f2[j];
34 }
35 int main() {
36     scanf("%d", &n);
37     for (int i = 1; i <= n; ++i)
38         f1[i] = calc_f1(i);
39     for (int i = 1; i <= n; ++i)
40         f2[i] = calc_f2(i);
41     convolute();
42     printf("%d\N", f3[n]);
43     return 0;
44 }
说明：对于 未定义行为，你可以理解为执行某条语句之后会出现 不确定情况。例如，数组越界就是典型的未定义行为。

1. A。
2. B。
3. A。
4. B。
5. B。
6. D。
这段代码计算了一个类莫比乌斯函数的构成的数列 $f1[i]$ 和一个 $f2[i]=i$ 的序列，并且对其进行卷积运算。需要注意的一些地方为：
1. scanf, printf 等函数也被定义在了 iostream 库中，所以在没有 cstdio 库删掉 iostream 库也会编译错误。
2. 调和级数 $T(n) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} = O(logn)$ 。

Question

1. 若将程序第 31 行的 n/i 改为 n 后运行，且已知程序可以安全地运行至第 36 行而不发生任何 未定义行为，则程序输出相对于修改前不变。( )

2. 去掉程序第 3 行，程序依然可以正常编译。( )

3. 若输入 1003 ，程序的输出为 ( )。

4. 该程序中，第 $30 \sim 33$ 行运行的时间复杂度为 ( )。

5. 若输入 3，程序的输出为 ( )。

6. 若输入 1000000 ，程序输出为 ( )。