csp信奥赛C++之约数研究
csp信奥赛C++之约数研究
原题说明：洛谷P1403 [AHOI2005] 约数研究
题目描述
科学家们在 Samuel 星球上的探险得到了丰富的能源储备，这使得空间站中大型计算机 Samuel II 的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩，小联被允许用 Samuel II 进行数学研究。
小联最近在研究和约数有关的问题，他统计每个正数N NN的约数的个数，并以f ( N ) f(N)f(N)来表示。例如12 1212的约数有1 , 2 , 3 , 4 , 6 , 12 1,2,3,4,6,121,2,3,4,6,12，因此f ( 12 ) = 6 f(12)=6f(12)=6。下表给出了一些f ( N ) f(N)f(N)的取值：
| N NN | 1 11 | 2 22 | 3 33 | 4 44 | 5 55 | 6 66 |
|---|---|---|---|---|---|---|
| f ( N ) f(N)f(N) | 1 11 | 2 22 | 2 22 | 3 33 | 2 22 | 4 44 |
现在请你求出：
∑ i = 1 n f ( i ) \sum_{i=1}^n f(i)i=1∑nf(i)
输入格式
输入一个整数n nn。
输出格式
输出答案。
输入输出样例 1
输入 1
3输出 1
5说明/提示
- 对于20 % 20\%20%的数据，N ≤ 5000 N \leq 5000N≤5000；
- 对于100 % 100\%100%的数据，1 ≤ N ≤ 10 6 1 \leq N \leq 10^61≤N≤106。
暴力代码
#include<bits/stdc++.h>usingnamespacestd;intn,sum=0;// n 为输入上限，sum 累计所有 f(i) 的和// 计算 x 的约数个数intf(intx){intcnt=0;// 约数计数器// 只需枚举到 sqrt(x) 即可成对统计for(inti=1;i<=sqrt(x);i++){if(x%i==0){// i 是 x 的约数cnt+=2;// 将 i 和 x/i 这一对都计入}if(i*i==x){// 若 i 恰好等于 x/i，说明是平方数，之前多算了一次cnt--;// 减去重复的一次}}returncnt;}intmain(){cin>>n;// 输入 n// 枚举 1 到 n 的每个数，累加它们的约数个数for(inti=1;i<=n;i++){sum+=f(i);}cout<<sum;// 输出结果return0;}暴力代码TLE 原因分析
- 数据范围：题目中 (n) 最大可达10 6 10^6106。
- 外层循环：共执行n = 10 6 n = 10^6n=106次。
- 内层函数
f(i)：对于每个 i，需要循环i \sqrt{i}i次（取整）。
总计算量约为：∑ i = 1 n i ≈ ∫ 0 n x d x = 2 3 n 3 / 2 \sum_{i=1}^{n} \sqrt{i} \approx \int_{0}^{n} \sqrt{x} \, dx = \frac{2}{3} n^{3/2}∑i=1ni≈∫0nxdx=32n3/2
代入 (n = 10^6)：
2 3 × ( 10 6 ) 3 / 2 = 2 3 × 10 9 ≈ 6.67 × 10 8 \frac{2}{3} \times (10^6)^{3/2} = \frac{2}{3} \times 10^9 \approx 6.67 \times 10^832×(106)3/2=32×109≈6.67×108
即大约 6.7 亿次循环迭代。 - 结论：暴力枚举每个数的约数个数的方法在n = 10 6 n=10^6n=106时无法通过时限，必须采用更高效的数学方法（如统计每个约数出现的次数）。
优化思路分析
更高效的方法：转换角度，统计每个正整数 d作为约数出现在多少个 i 中。
对于给定的 d，在1 ∼ n 1 \sim n1∼n中，d 的倍数有⌊ n d ⌋ \left\lfloor \frac{n}{d} \right\rfloor⌊dn⌋个，因此 d对总和的贡献就是⌊ n d ⌋ \left\lfloor \frac{n}{d} \right\rfloor⌊dn⌋。
于是：∑ i = 1 n f ( i ) = ∑ d = 1 n ⌊ n d ⌋ \sum_{i=1}^n f(i) = \sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor∑i=1nf(i)=∑d=1n⌊dn⌋
直接循环 d = 1 到 n 累加即可，时间复杂度 O(n)，空间复杂度 O(1)。
对于n ≤ 10 6 n \le 10^6n≤106，完全可行。
AC代码
#include<bits/stdc++.h>// 万能头文件usingnamespacestd;intmain(){intn;// 输入的上限scanf("%d",&n);// 读入 nlonglongans=0;// 答案可能超出 int 范围，使用 long long// 枚举每个可能的约数 d，统计它出现的次数并累加for(intd=1;d<=n;++d){ans+=n/d;// d 作为约数出现的次数 = floor(n / d)}printf("%lld\n",ans);// 输出结果return0;}【文末福利：一等奖秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
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信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：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;}