2021年CSP-J初赛真题及答案解析(阅读程序3)

2026/8/13 13:19:50 拓冰建站浏览量

2021年CSP-J初赛真题及答案解析(阅读程序3)

第3题

#include<iostream>usingnamespacestd;constintn=100000;constintN=n+1;intm;inta[N],b[N],c[N],d[N];intf[N],g[N];voidinit(){f[1]=g[1]=1;//此处为13行for(inti=2;i<=n;i++){if(!a[i]){b[m++]=i;c[i]=1,f[i]=2;d[i]=1,g[i]=i+1;}for(intj=0;j<m&&b[j]*i<=n;j++){intk=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);//此处为25行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);}}}}intmain(){init();intx;cin>>x;cout<<f[x]<<' '<<g[x]<<endl;return0;}

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

判断题（每题 1.5 分）

若输入不为 1，把第 13 行删去不会影响输出的结果。（）
- A. 正确 B. 错误
第 25 行的f[i] / c[i * k]可能存在无法整除而向下取整的情况。（）
- A. 正确 B. 错误
在执行完init()后，f数组不是单调递增的，但g数组是单调递增的。（）
- A. 正确 B. 错误

单选题

init函数的时间复杂度为（）。
- A. O(n) B.O ( n log ⁡ n ) O(n\log n)O(nlogn)C.O ( n n ) O(n\sqrt{n})O(nn)D.O ( n 2 ) O(n^2)O(n2)
在执行完init()后，f[1], f[2], f[3], …, f[100]中有（）个等于 2。
- A. 23 B. 24 C. 25 D. 26
当输入为1000时，输出为（）。
- A.15 1340B.15 2340C.16 2340D.16 1340

答案与解析

1. 答案：A（正确）
解析：第 13 行为f[1] = g[1] = 1;，其作用仅为初始化f[1]和g[1]。题目限定输入x不为 1，即x ≥ 2，程序只会输出f[x]和g[x]，不会访问f[1]和g[1]。因此删去该行不会影响输出结果。

2. 答案：B（错误）
解析：第 25 行f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);中，c[i * k] = c[i] + 1，此时i含有质因子k的指数为c[i]。约数个数的递推公式要求整除性：原约数个数f[i]必包含因子(c[i] + 1)，因此f[i] / (c[i] + 1)可整除，不可能出现向下取整的情况。

3. 答案：B（错误）
解析：f是约数个数函数，显然不单调（如f[6]=4 > f[7]=2）。g是约数和函数，同样不单调（如g[6]=12 > g[7]=8）。因此“g数组单调递增”的说法错误。

4. 答案：A（O(n)）
解析：程序使用线性筛（欧拉筛），每个合数仅被其最小质因子标记一次，内层循环总次数与n成正比，因此时间复杂度为O(n)。

5. 答案：C（25）
解析：f[i] = 2当且仅当i为素数（约数个数为 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）。注意f[1]=1，不计算在内。

6. 答案：C（16 2340）
解析：1000 = 2³ × 5³。

约数个数：(3+1)×(3+1) = 16。
约数和：(1+2+4+8) × (1+5+25+125) = 15 × 156 = 2340。
因此输出为16 2340。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

建站实战干货

2021年CSP-J初赛真题及答案解析(阅读程序3)