2023年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

2023年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）

第 2 题

#include<iostream>#include<cmath>#include<vector>#include<algorithm>usingnamespacestd;longlongsolve1(intn){vector<bool>p(n+1,true);vector<longlong>f(n+1,0),g(n+1,0);f[1]=1;for(inti=2;i*i<=n;i++){if(p[i]){vector<int>d;for(intk=i;k<=n;k*=i)d.push_back(k);reverse(d.begin(),d.end());for(intk:d){for(intj=k;j<=n;j+=k){if(p[j]){p[j]=false;f[j]=i;g[j]=k;}}}}}for(inti=sqrt(n)+1;i<=n;i++){if(p[i]){f[i]=i;g[i]=i;}}longlongsum=1;for(inti=2;i<=n;i++){f[i]=f[i/g[i]]*(g[i]*f[i]-1)/(f[i]-1);sum+=f[i];}returnsum;}longlongsolve2(intn){longlongsum=0;for(inti=1;i<=n;i++){sum+=i*(n/i);}returnsum;}intmain(){intn;cin>>n;cout<<solve1(n)<<endl;cout<<solve2(n)<<endl;return0;}

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

判断题

1. 将第 15行删去，输出不变。（）

   A. 正确 B. 错误

2. 当输入为10时，输出的第一行大于第二行。（）

   A. 正确 B. 错误

3. （2 分） 当输入为1000时，输出的第一行与第二行相等。（）

   A. 正确 B. 错误

单选题

1. solve1(n)的时间复杂度为（）。

   A. O(nlog⁡2 ^22n) B. O(n) C. O(nlog⁡n) D. O(nlog⁡log⁡n)

2. solve2(n)的时间复杂度为（）。

   A. O(n2 ^22) B. O(n) C. O(nlog⁡n) D. O(nn ) \sqrt{n})n​))

3. 当输入为5时，输出的第二行为（）。

   A.20B.21C.22D.23

代码分析

• solve1(n)通过筛法标记每个数的最小质因数及其最高幂次，再利用公式递推计算除数之和σ ( i ) \sigma(i)σ(i)，最后求和。
• solve2(n)直接计算∑ i = 1 n i × ⌊ n / i ⌋ \sum_{i=1}^n i \times \lfloor n/i \rfloor∑i=1n​i×⌊n/i⌋，该和式等价于∑ k = 1 n σ ( k ) \sum_{k=1}^n \sigma(k)∑k=1n​σ(k)。
• 两函数计算结果相同，时间复杂度分别为O ( n log ⁡ log ⁡ n ) O(n \log \log n)O(nloglogn)和O ( n ) O(n)O(n)。

判断题答案

1. B. 错误
   删去第15行（reverse(d.begin(), d.end());）后，d中i的幂次变为从小到大排列，会导致g[j]被错误地赋值为较小的幂次，进而使得后续计算的f[i]（即除数之和）错误，输出改变。

2. B. 错误
   solve1(n)和solve2(n)均计算1 11到n nn所有数的除数之和∑ k = 1 n σ ( k ) \sum_{k=1}^n \sigma(k)∑k=1n​σ(k)，因此两行输出相等。当输入为10时，第一行等于第二行。

3. A. 正确
   同理，当输入为1000时，两行输出相等。

单选题答案

1. D. O(nloglogn)
   solve1(n)的第一部分类似于筛法，仅处理≤ n \leq \sqrt{n}≤n​的质数及其幂次，遍历倍数的总次数约为n ∑ p ≤ n 1 / p = O ( n log ⁡ log ⁡ n ) n \sum_{p \leq \sqrt{n}} 1/p = O(n \log \log n)n∑p≤n​​1/p=O(nloglogn)，其余部分为O ( n ) O(n)O(n)，故总时间复杂度为O ( n log ⁡ log ⁡ n ) O(n \log \log n)O(nloglogn)。

2. B. O(n)
   solve2(n)通过单层循环计算，循环次数为n nn，每次操作O ( 1 ) O(1)O(1)，故时间复杂度为O ( n ) O(n)O(n)。

3. B. 21
   当输入为5时，solve2(5)计算过程为：
   1 × ⌊ 5 / 1 ⌋ + 2 × ⌊ 5 / 2 ⌋ + 3 × ⌊ 5 / 3 ⌋ + 4 × ⌊ 5 / 4 ⌋ + 5 × ⌊ 5 / 5 ⌋ = 5 + 4 + 3 + 4 + 5 = 21 1 \times \lfloor 5/1 \rfloor + 2 \times \lfloor 5/2 \rfloor + 3 \times \lfloor 5/3 \rfloor + 4 \times \lfloor 5/4 \rfloor + 5 \times \lfloor 5/5 \rfloor = 5 + 4 + 3 + 4 + 5 = 211×⌊5/1⌋+2×⌊5/2⌋+3×⌊5/3⌋+4×⌊5/4⌋+5×⌊5/5⌋=5+4+3+4+5=21。

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

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、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

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

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、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

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

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

· 文末祝福 ·

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