2021年CSP-J初赛真题及答案解析(阅读程序3)第3题#includeiostreamusingnamespacestd;constintn100000;constintNn1;intm;inta[N],b[N],c[N],d[N];intf[N],g[N];voidinit(){f[1]g[1]1;//此处为13行for(inti2;in;i){if(!a[i]){b[m]i;c[i]1,f[i]2;d[i]1,g[i]i1;}for(intj0;jmb[j]*in;j){intkb[j];a[i*k]1;if(i%k0){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]*kd[i];break;}else{c[i*k]1;f[i*k]2*f[i];d[i*k]g[i];g[i*k]g[i]*(k1);}}}}intmain(){init();intx;cinx;coutf[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. 答案AO(n)解析程序使用线性筛欧拉筛每个合数仅被其最小质因子标记一次内层循环总次数与n成正比因此时间复杂度为O(n)。5. 答案C25解析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. 答案C16 2340解析1000 2³ × 5³。约数个数(31)×(31) 16。约数和(1248) × (1525125) 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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}