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 NN1 112 223 334 445 556 66f ( N ) f(N)f(N)1 112 222 223 332 224 44现在请你求出∑ i 1 n f ( i ) \sum_{i1}^n f(i)i1∑nf(i)输入格式输入一个整数n nn。输出格式输出答案。输入输出样例 1输入 13输出 15说明/提示对于20 % 20\%20%的数据N ≤ 5000 N \leq 5000N≤5000对于100 % 100\%100%的数据1 ≤ N ≤ 10 6 1 \leq N \leq 10^61≤N≤106。暴力代码#includebits/stdc.husingnamespacestd;intn,sum0;// n 为输入上限sum 累计所有 f(i) 的和// 计算 x 的约数个数intf(intx){intcnt0;// 约数计数器// 只需枚举到 sqrt(x) 即可成对统计for(inti1;isqrt(x);i){if(x%i0){// i 是 x 的约数cnt2;// 将 i 和 x/i 这一对都计入}if(i*ix){// 若 i 恰好等于 x/i说明是平方数之前多算了一次cnt--;// 减去重复的一次}}returncnt;}intmain(){cinn;// 输入 n// 枚举 1 到 n 的每个数累加它们的约数个数for(inti1;in;i){sumf(i);}coutsum;// 输出结果return0;}暴力代码TLE 原因分析数据范围题目中 (n) 最大可达10 6 10^6106。外层循环共执行n 10 6 n 10^6n106次。内层函数f(i)对于每个 i需要循环i \sqrt{i}i次取整。总计算量约为∑ i 1 n i ≈ ∫ 0 n x d x 2 3 n 3 / 2 \sum_{i1}^{n} \sqrt{i} \approx \int_{0}^{n} \sqrt{x} \, dx \frac{2}{3} n^{3/2}∑i1ni≈∫0nxdx32n3/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/232×109≈6.67×108即大约 6.7 亿次循环迭代。结论暴力枚举每个数的约数个数的方法在n 10 6 n10^6n106时无法通过时限必须采用更高效的数学方法如统计每个约数出现的次数。优化思路分析更高效的方法转换角度统计每个正整数 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_{i1}^n f(i) \sum_{d1}^n \left\lfloor \frac{n}{d} \right\rfloor∑i1nf(i)∑d1n⌊dn⌋直接循环 d 1 到 n 累加即可时间复杂度 O(n)空间复杂度 O(1)。对于n ≤ 10 6 n \le 10^6n≤106完全可行。AC代码#includebits/stdc.h// 万能头文件usingnamespacestd;intmain(){intn;// 输入的上限scanf(%d,n);// 读入 nlonglongans0;// 答案可能超出 int 范围使用 long long// 枚举每个可能的约数 d统计它出现的次数并累加for(intd1;dn;d){ansn/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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
)
