2023 CSP-S 阅读程序2
判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）
01 #include <iostream>
02 #include <cmath>
03 #include <vector>
04 #include <algorithm>
05 using namespace std;
06
07 long long solve1(int n) {
08 vector<bool> p(n + 1, true);
09 vector<long long> f(n + 1, 0), g(n + 1, 0);
10 f[1] = 1;
11 for (int i = 2; i * i <= n; i++) {
12 if (p[i]) {
13 vector<int> d;
14 for (int k = i; k <= n; k *= i) d.push_back(k);
15 reverse(d.begin(), d.end());
16 for (int k : d) {
17 for (int j = k; j <= n; j += k) {
18 if (p[j]) {
19 p[j] = false;
20 f[j] = i;
21 g[j] = k;
22 }
23 }
24 }
25 }
26 }
27 for (int i = sqrt(n) + 1; i <= n; i++) {
28 if (p[i]) {
29 f[i] = i;
30 g[i] = i;
31 }
32 }
33 long long sum = 1;
34 for (int i = 2; i <= n; i++) {
35 f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
36 sum += f[i];
37 }
38 return sum;
39 }
40
41 long long solve2(int n) {
42 long long sum = 0;
43 for (int i = 1; i <= n; i++) {
44 sum += i * (n / i);
45 }
46 return sum;
47 }
48
49 int main() {
50 int n;
51 cin >> n;
52 cout << solve1(n) << endl;
53 cout << solve2(n) << endl;
54 return 0;
55 }
假设输入的 n是不超过 1000000的自然数，完成下面的判断题和单选题:
判断题
1 将第 15 行删去，输出不变( )
2 当输入为 10 时，输出的第一行大于第二行( )
3 （2 分） 当输入为 1000 时，输出的第一行与第二行相等( )
单选题
4 solve1(n) 的时间复杂度为( )
A O(nlog2n)
B O(n)
C O(nlogn)
D O(nloglogn)
5 solve2(n) 的时间复杂度为( )
A O(n^2)
B O(n)
C O(nlogn)
D O(nsqrt(n))
6 当输入为 5 时，输出的第二行为( )
A 20
B 21
C 22
D 23
2 相关知识点
1) vector 数组
#include<bits/stdc++.h>
using namespace std;
vector<int> a(11,1);//声明数组a并赋值1
vector<int> b(11);//声明数组a,默认赋值0
int main(){
a.push_back(2);//在a最后一个元素后面追加2
a.push_back(4);//在a最后一个元素后面追加4
for(int i=0;i<a.size();i++){//输出a数组中每个元素
cout <<a[i]<< ' ';
}
cout<<endl;
for(int i=0;i<b.size();i++){//输出b数组中每个元素
cout <<b[i]<< ' ';C++
}
return 0;
}
/*
输出
1 1 1 1 1 1 1 1 1 1 1 2 4
0 0 0 0 0 0 0 0 0 0 0
*/
2) reverse函数
reverse 函数主要用于反转字符串（字符数组）的数据类型
#include<bits/stdc++.h>
using namespace std;
int main() {
std::vector<int> d;
// 向向量d中添加一些元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
// 使用范围for循环遍历向量d中的元素
for (int k : d) {
std::cout<< k << " ";
}
printf("\n");
reverse(d.begin(), d.end());
for (int k : d) {
std::cout<< k << " ";
}
printf("\n");
string s="abcde";
//顺序输出s
cout<<s;
printf("\n");
reverse(s.begin(), s.end());
//反转输出s
cout<<s;
return 0;
}
/*
1 2 3
3 2 1
abcde
edcba
*/
3) 埃式筛法
如果一个数是素数，那么它的倍数一定不是素数。我们要找n以内的所有素数，那么把n以内的合数全部筛掉，剩下的就是素数了
时间复杂度
O(n * log (log n) )
欧拉筛法
将合数分解为一个最小质数乘以另一个数的形式，即 合数 = 最小质数 * 自然数，然后通过最小质数来判断当前数是否被标记过
时间复杂度
O(n)
4) 约数和
质数
质数和合数是数学中对于自然数（不包括0和1）的两种重要分类
质数 (Prime Number)
一个大于1的自然数，除了1和它本身以外不再有其他因数的数称为质数
例如
2、3、5、7、11、13、17、19等都是质数
注意
质数只有两个正因数：1和它本身
合数
合数是指在大于1的整数中，除了能被1和本身整除外，还能被其他数（0除外）整除的数
4、6、8、9、10、12、14、15等都是合数
注意
合数至少有三个正因数，除1和本身以外还有至少一个正因数
唯一分解定理
唯一分解定理又称为算术基本定理，其性质是每个大于1的自然数N（非质数）均可以被分解且他们的分解形式是唯一的
任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1 * P2^a2 * P3^a3 … Pn^an，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式
例如
18 = 2^1 * 3^2
约数
约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
例如
6的正约数有：1、2、3、6
10的正约数有：1、2、5、10
约数个数
每个合数都可以分解成质因子的幂次的乘积
H = p1^a1 * p2^a2 ....pn^an 其中 pi都是质数，ai是幂次，p1是最小的质数
约数的个数为(a1+1)*(a2+1)*...(an+1)
例题
18 = 2^1 * 3^2
约数的个数为(a1+1)*(a2+1) = (1+1) * (2+1) =2 * 3 =6
分析
18由2个质数组成，分别为2和3
2可以包括2^0和2^1 这2种情况(可能出现的情况包括2的0次幂，所以为幂次+1)
3可以包括3^0、3^1、3^2 这3种情况(可能出现的情况包括3的0次幂，所以为幂次+1)
根据乘法原理 2 * 3 =6种情况
2^0 * 3^0 = 1 * 1= 1
2^1 * 3^0 = 2 * 1= 2
2^0 * 3^1 = 1 * 3= 3
2^1 * 3^1 = 2 * 3= 6
2^0 * 3^2 = 1 * 9= 9
2^1 * 3^2 = 1 * 9= 18
约数和
每个合数都可以分解成质因子的幂次的乘积
H = p1^a1 * p2^a2 ....pn^an 其中 pi都是质数，ai是幂次，p1是最小的质数
约数的和为(p1^0+p1^1+...p1^a1)*(p2^0+p2^1+...p2^a2)*...(pn^0+pn^1+...p2^an)
例如
12 =2^2*3^1
枚举约数
1 =2^0*3^0
2 =2^1*3^0
4 =2^2*3^0
3 =2^0*3^1
6 =2^1*3^1
12 =2^2*3^1
1+2+4=2^0*3^0 + 2^1*3^0 + 2^2*3^0=3^0 * (2^0+2^1+2^2)
3+6+12 = 2^0*3^1 + 2^1*3^1 + 2^2*3^1 = 3^1 * (2^0+2^1+2^2)
1+2+4+3+6+12=3^0 * (2^0+2^1+2^2) + 3^1 * (2^0+2^1+2^2) =(2^0+2^1+2^2)*(3^0+3^1)=28
例题
18 = 2^1 * 3^2
根据约数和公式
约数和=(2^0+2^1)*(3^0+3^1+3^2)=3 * 13 =39
枚举18的约数和=1+2+3+6+9+18=39
3 思路分析
1 solve1和solve2 这2个函数都是求，参数n中，1~n每个数的约数和的累加和
例如 n=3时
1的约数和为1
2的约数和为3
3的约数和为4
所以3的约数和的累加和为1+3+4=8
2 solve1实现思路
1)通过埃氏筛法求素数，存入动态数组p中
2)f数组存入每个数的最小质数
3)g数组存入每个数的最小质数的幂次数，例如 12=2*2*3 最小质数为2，最小质数有2个2，为2^2,对应幂次数为4
4)找个每个素数的所有幂次数，2 4 8 16
5)对上面幂次数反转，变成16 8 4 2，目的是，最小质数幂次数取最大值，设置p[i]=false
例如g[4]=4,g[8]=8,不反转的话， g[4]=2，g[8]=2
6) 上面把f和g数组的2~sqrt(n)数据填充好了，下面代码把sqrt(n)~n的f和g数组填充
27 for (int i = sqrt(n) + 1; i <= n; i++) {
28 if (p[i]) {
29 f[i] = i;
30 g[i] = i;
31 }
32 }
7) 通过f和g数组计算约数和
约数和=最小质因数约数和 * 除最小质因数外的约数和
例如12=2*2*3
约数和：(2^0+2^1+2^2)*(3^0+3^1) = (1+2+4)*(1+3)=28
例如60=2*2*3*5
约数和：(2^0+2^1+2^2)*(3^0+3^1)*(5^0+5^1) = (1+2+4)*(1+3)*(1+5)=168
对应如下程序
(g[i] * f[i] - 1) / (f[i] - 1)是计算最小质因数约数和
例如求12的约数和
最小质因数约数和
2^0+2^1+2^2 -是一个等比数列，首项为1，公比为2，根据等比数列求和
(1-2^3)/(1-2)=(2^3-1)/(2-1)=7
(g[12]*f[12]-1)/(f[12] - 1)
=(4*2-1)/(2-1)=7
(g[i] * f[i] - 1) / (f[i] - 1) 满足上面等比数列求和公式
f[60]=f[60/g[60]] * (g[60]*f)
其他约数和
f[i / g[i]]=f[12/g[12]]=f[12/4]=f[3]
由于f数组是每次计算约数和，求f[12]时，f[3]约数和已经计算出了，为1+3=4
因此
f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);是计算i的约数和
sum开始为1，是1的约数和，如下循环结束后，计算了2~n的每个约数和累加到sum中
因此sum是1~n所有数的约数和的累加和
33 long long sum = 1;
34 for (int i = 2; i <= n; i++) {
35 f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
36 sum += f[i];
37 }
2 solve2实现思路
一个数k，在1~n范围内作为约数出现，必然是在k，2k，3k....中
因此作为此约数出现的次数为⌊n/k⌋，k的所有约数和为：k * ⌊n/k⌋
for 循环累加1~n所有约数的和，因此等同于solve2
41 long long solve2(int n) {
42 long long sum = 0;
43 for (int i = 1; i <= n; i++) {
44 sum += i * (n / i);
45 }
46 return sum;
47 }
假设输入的 n是不超过 1000000的自然数，完成下面的判断题和单选题:
判断题
1 将第 15 行删去，输出不变( F )
分析
g[i]目的是计算最小质数幂次数取最大值
不反转的话g[i]最小质数幂次数取最小值
例如
g[8]=8
如果不反转
g[8]=2
因此是错误的
2 当输入为 10 时，输出的第一行大于第二行( F )
分析
第1行和第2行都是求1~10的所有数的约数和的累加和，这2个数相等
因此是错误的
3 （2 分） 当输入为 1000 时，输出的第一行与第二行相等( T )
分析
第1行和第2行都是求1~1000的所有数的约数和的累加和，这2个数相等
因此是正确的
单选题
4 solve1(n) 的时间复杂度为( D )
A O(nlog2n)
B O(n)
C O(nlogn)
D O(nloglogn)
分析
solve1时间复杂度最大在埃氏筛法找质数
埃氏筛法是根据质数把其余合数筛掉，保留下来的为质数
由于质数的个数为loglogn，筛去的合数为n-loglogn等同于n
因此时间复杂度为n*loglogn
所以选D
5 solve2(n) 的时间复杂度为( B )
A O(n^2)
B O(n)
C O(nlogn)
D O(nsqrt(n))
分析
solve2的时间复杂度主要为for循环，因此时间复杂度为O(n)
41 long long solve2(int n) {
42 long long sum = 0;
43 for (int i = 1; i <= n; i++) {
44 sum += i * (n / i);
45 }
46 return sum;
47 }
6 当输入为 5 时，输出的第二行为( B )
A 20
B 21
C 22
D 23
分析
第2行主要调用solve2函数，计算1~5这5个数每个数约数和的累加和
i=1时 i*(n/i)=1*(5/1)=5
i=2时 i*(n/i)=2*(5/2)=2*2=4
i=3时 i*(n/i)=3*(5/3)=3*1=3
i=4时 i*(n/i)=4*(5/4)=4*1=4
i=5时 i*(n/i)=5*(5/5)=5*1=5
sum=5+4+3+4+5=21
所以选B
41 long long solve2(int n) {
42 long long sum = 0;
43 for (int i = 1; i <= n; i++) {
44 sum += i * (n / i);
45 }
46 return sum;
47 }