信息学奥赛初赛天天练-38-CSP-J2021阅读程序-约数个数、约数和、埃氏筛法、欧拉筛法筛素数应用

PDF文档公众号回复关键字:20240628

2021 CSP-J 阅读程序3

1阅读程序(判断题1.5分 选择题3分 共计40分 )

01 #include<stdio.h>
02 using namespace std;
03
04 #define n 100000
05 #define N n+1
06 
07 int m;
08 int a[N],b[N],c[N],d[N];
09 int f[N],g[N];
10 
11 void init()
12 {
13	 f[1]=g[1]=1;
14	 for(int i=2;i<=n;i++){
15	 	if(!a[i]){
16			b[m++]=i;
17			c[i]=1,f[i]=2;
18			d[i]=1,g[i]=i+1;
19		}
20		for(int j=0;j<m&&b[j]*i<=n;j++){
21			int k=b[j];
22			a[i*k]=1;
23			if(i%k==0){
24				c[i*k]=c[i]+1;
25				f[i*k]=f[i]/c[i*k]*(c[i*k]+1);
26				d[i*k]=d[i];
27				g[i*k]=g[i]*k+d[i];
28				break;
29			}
30			else{
31				c[i*k]=1;
32				f[i*k]=2*f[i];	
33				d[i*k]=g[i];
34				g[i*k]=g[i]*(k+1);
35			}
36		}
37	 }
38 }
39
40 int main()
41 {
42	 init();
43	
44	 int x;
45	 scanf("%d",&x);
46	 printf("%d %d\n",f[x],g[x]);
47	 return 0;
48 }

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

判断题

28.若输入不为"1"，把第13删去不会影响输出的结果( )

29.(2分) 第25行的"f[i]/c[i*k]"可能存在的无法整除而向下取取整的情况( )

30.(2分)在执行完init()后，f数组不是单调递增的，但g数组是单调递增的( )

单选题

31.init 函数的时间复杂度为( )

A. O(n)

B. O(nlogn)

C. O(n sqrt(n))

D. O(n^2)

32.在执行完init()后，f[1],f[2],f[3]… f[100]中有( )个等于2.

A. 23

B. 24

C. 25

D. 26

33.(4分)当输入为"1000"时，输出为( )

A. “15 1340”

B. “15 2340”

C. “16 2340”

D. “16 1340”

2 相关知识点

埃式筛法

如果一个数是素数，那么它的倍数一定不是素数。我们要找n以内的所有素数，那么把n以内的合数全部筛掉，剩下的就是素数了

时间复杂度

O(n * log (log n) )

欧拉筛法

将合数分解为一个最小质数乘以另一个数的形式，即 合数 = 最小质数 * 自然数，然后通过最小质数来判断当前数是否被标记过

时间复杂度

O(n)

3 思路分析

分析

本程序通过欧拉筛求约数个数及其约数和

使用到的对应数组

标记a数组，对合数进行标记，未标记的则是质数

质数表b数组，从小到大知道质数写到b数组

约数个数f数组，记录一个数对应的约数的个数

在填入约数个数f数组时，使用到最小质因数个数c数组

在填入约数和g数组时，使用到约数和对应的连乘积除第1项外的其他连乘积d数组

约数和g数组，记录一个数对应的约数之和

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

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

判断题

28.若输入不为"1"，把第13删去不会影响输出的结果( T )

分析

13行程序计算并未使用，只对f[1],g[1]输出有影响，如果不输出f[1],g[1]，不会影响输出

所以输入不为"1"，删除不影响输出结果

29.(2分) 第25行的"f[i]/c[i*k]"可能存在的无法整除而向下取取整的情况( F )

分析

c[i]表示i的最小质因数个数
f[i]表示i的约数个数，计算公式如下H = p1^a1 * p2^a2 ....pn^an 其中 pi都是质数，ai是幂次，p1是最小的质数
约数的个数f[i]=(a1+1)*(a2+1)*...(an+1)
其中a1是最小质因数个数
c[i]表示i的最小质因数个数=a1
满足条件i%k==0
c[i*k]=相当于最小质数+1=a1+1
a1+1是f[i]的因子，所以f[i]/c[i*k]不会存在无法整除的情况
所以错误

30.(2分)在执行完init()后，f数组不是单调递增的，但g数组是单调递增的( F )

分析

f数组是约数个数，合数个数多，质数个数少，3 4 5 对应约数个数分别是2 3 2 看，并不是单调递增的

g数组是约数和，3 4 5 对应约数和分别是4 7 6 看，并不是单调递增的

单选题

31.init 函数的时间复杂度为( A )

A. O(n)

B. O(nlogn)

C. O(n sqrt(n))

D. O(n^2)

分析

此算法是欧拉筛法求质数，欧拉筛是线性筛法，即所有的合数都被它最小的质因子筛一次，减少了埃氏筛法的重复筛的次数，时间复杂度近似O(n)

32.在执行完init()后，f[1],f[2],f[3]… f[100]中有( C )个等于2.

A. 23

B. 24

C. 25

D. 26

分析

f数组是约数个数，约数个数和为2，表示对应数组下标的数为质数

1~100之间的质数有25个，分别是

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

33.(4分)当输入为"1000"时，输出为( C )

A. “15 1340”

B. “15 2340”

C. “16 2340”

D. “16 1340”

分析

由程序逻辑知分别输出1000对应的约数个数及其对应的约数和
1000=2^3 * 5^3第1项求约数个数，根据约数个数公式
(3+1)*(3+1)=16
第2项求约数和，根据约数和公式
(2^0+2^1+2^2+2^3) * (5^0+5^1+5^2+5^3)=2340
所以选C