CSPJ2021 阅读程序3
#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; } 假设输入的x是不超过1000的自然数,完成下面的判断题和单选题:
若输入不为“1”,把第12行删去不会影响输出的结果。( )
第24行的“f[i]/c[i*k]”可能存在无法整除而向下取整的情况。()
在执行完init()后,f数组不是单调递增的,但g数组是单调递增的。( )
init函数的时间复杂度为()。
Θ(n)
Θ(nlogn)
Θ(nsqrt(n))
Θ(n^2)
在执行完 init()后,f[1],f[2],f[3].....f[100]中有()个等于2。
23
24
25
26
当输入为“1000”时,输出为( )。
“15 1340”
“15 2340”
“16 2340”
“16 1340”
发表评论