QQ扫一扫联系
1 #include <stdio.h>
2
3 #define n 100000
4 #define N n+1
5
6 int m;
7 int a[N], b[N], c[N], d[N];
8 int f[N], g[N];
9
10 void init()
11 {
12 f[1] = g[1] = 1;
13 for (int i = 2; i <= n; i++) {
14 if (!a[i]) {
15 b[m++] = i;
16 c[i] = 1, f[i] = 2;
17 d[i] = 1, g[i] = i + 1;
18 }
19 for (int j = 0; j < m && b[j] * i <= n; j++) {
20 int k = b[j];
21 a[i * k] = 1;
22 if (i % k == 0) {
23 c[i * k] = c[i] + 1;
24 f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
25 d[i * k] = d[i];
26 g[i * k] = g[i] * k + d[i];
27 break;
28 }
29 else {
30 c[i * k] = 1;
31 f[i * k] = 2 * f[i];
32 d[i * k] = g[i];
33 g[i * k] = g[i] * (k + 1);
34 }
35 }
36 }
37 }
38
39 int main()
40 {
41 init();
42
43 int x;
44 scanf("%d", &x);
45 printf("%d %d\n", f[x], g[x]);
46 return 0;
47 }假设输入的x是不超过1000的自然数，完成下面的判断题和单选题：
?判断题
1）若输入不为”1”，把第12行删去不会影响输出的结果。（）
2）第24行f[i * k] = f[i] / c[i * k] * (c[i * k] + 1)中的” f[i]/c[i*k]”可能存在无法整除而
向下取整的情况。（）
3）在执行完init()后，f数组不是单调递增的，但g数组是单调递增的。（）
?单选题
4）init函数的时间复杂度为（）。
5）在执行完init()后，f[1], f[2], f[3] ...... f[100]中有（）个等于2。
6）当输入”1000”时，输出为（）。
1.A.正确B.错误
2.A.正确B.错误
3.A.正确B.错误
4.
A.O(n)
B.O(n log n)
C.O(n √n)
D.O(n^2)
5.
A.23
B.24
C.25
D.26
6.
A.”15 1340”
B.”15 2340”
C.”16 2340”
D.”16 1340”
第一空(1.5分)：__________________
第二空(2分)：__________________
第三空(2分)：__________________
第四空(3分)：__________________
第五空(3分)：__________________
第六空(4分)：__________________
