题解：瑞学堂 徐老师的连续正整数和

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂徐老师的连续正整数和【题目描述】徐老师发现有些正整数可以表示为一个或多个连续正整数的和。例如9 4 5 9459459 2 3 4 9234923415 7 8 1578157815 4 5 6 154561545615 1 2 3 4 5 15123451512345现在给定一个正整数n nn请你帮助徐老师计算有多少种不同的连续正整数序列至少包含两个数使得这些数的和恰好等于n nn。【输入】一行一个正整数n ( 1 ≤ n ≤ 10 5 ) n (1≤n≤10^5)n(1≤n≤105)。【输出】一行一个整数表示和为n nn的连续正整数序列长度至少为2 22的个数。【输入样例】9【输出样例】2【核心思想】问题分析给定正整数n nn求有多少个长度至少为2 22的连续正整数序列其和恰好等于n nn。这是一个数学推导 枚举优化问题关键在于利用等差数列求和公式将双重循环转化为单重循环将时间复杂度从O ( n 2 ) O(n^2)O(n2)优化到O ( n ) O(\sqrt{n})O(n​)。算法选择数学推导等差数列求和设连续序列首项为a aa长度为i iii ≥ 2 i \geq 2i≥2则n a ( a 1 ) ⋯ ( a i − 1 ) i ⋅ a i ( i − 1 ) 2 n a (a1) \dots (ai-1) i \cdot a \frac{i(i-1)}{2}na(a1)⋯(ai−1)i⋅a2i(i−1)​变形得n − i ( i − 1 ) 2 i ⋅ a n - \frac{i(i-1)}{2} i \cdot an−2i(i−1)​i⋅a即a n − i ( i − 1 ) 2 i a \frac{n - \frac{i(i-1)}{2}}{i}ain−2i(i−1)​​单重枚举枚举序列长度i ii判断剩余值是否能被i ii整除且首项a 0 a 0a0关键步骤公式变形由n i ⋅ a i ( i − 1 ) 2 n i \cdot a \frac{i(i-1)}{2}ni⋅a2i(i−1)​得a n − i ( i − 1 ) 2 i a \frac{n - \frac{i(i-1)}{2}}{i}ain−2i(i−1)​​枚举长度i ii从2 22开始终止条件i ( i − 1 ) 2 n \frac{i(i-1)}{2} n2i(i−1)​n计算r e m n − i ( i − 1 ) 2 rem n - \frac{i(i-1)}{2}remn−2i(i−1)​若r e m 0 rem 0rem0且r e m m o d i 0 rem \bmod i 0remmodi0则存在合法首项a r e m i a \frac{rem}{i}airem​ans终止条件分析当i ( i − 1 ) 2 ≥ n \frac{i(i-1)}{2} \geq n2i(i−1)​≥n时r e m ≤ 0 rem \leq 0rem≤0首项非正无需继续枚举输出答案a n s ansans时间/空间复杂度时间复杂度O ( n ) O(\sqrt{n})O(n​)由i ( i − 1 ) 2 n \frac{i(i-1)}{2} n2i(i−1)​n得i O ( n ) i O(\sqrt{n})iO(n​)空间复杂度O ( 1 ) O(1)O(1)仅使用常数变量数学优化的核心思想消元降维通过等差数列公式将枚举首项 枚举末项的双重循环转化为枚举长度 验证整除的单重循环利用代数变形消除一个维度整除约束转存在性将是否存在正整数首项a aa转化为剩余值r e m remrem是否为i ii的正倍数避免实际计算a aa终止条件的紧界i ( i − 1 ) 2 n \frac{i(i-1)}{2} n2i(i−1)​n确保r e m 0 rem 0rem0且a 0 a 0a0同时限制枚举范围在O ( n ) O(\sqrt{n})O(n​)连续和问题的通用技巧n nn表示为连续i ii个整数之和等价于n nn存在奇因子或特定分解形式本题通过直接枚举长度实现适用于连续序列和类问题核心在于利用求和公式建立长度与首项的关系通过整除性判断解的存在性【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免累加和溢出intn,ans;// n为给定的正整数ans记录满足条件的连续正整数序列个数signedmain()// 使用signed main配合#define int long long{cinn;// 读入正整数n// 枚举连续序列的起点afor(inta1;an;a)// a为连续序列的第一个数{intsum0;// sum记录当前连续序列的累加和// 从起点a开始向后累加枚举序列的终点bfor(intba;bn;b)// b为连续序列的当前累加到的数{sumb;// 将b加入累加和if(sumn)// 如果累加和已经超过nbreak;// 后续b更大sum只会更大直接退出内层循环if(sumnba)// 如果累加和恰好等于n且序列长度至少为2baans;// 找到一个满足条件的连续序列答案加1}}coutansendl;// 输出满足条件的连续正整数序列个数return0;}// 时间优化的版本#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免中间计算溢出intn,ans;// n为给定的正整数ans记录满足条件的连续正整数序列个数signedmain()// 使用signed main配合#define int long long{cinn;// 读入正整数n// 数学推导设连续序列长度为i首项为a// 则 n a (a1) ... (ai-1) i*a i*(i-1)/2// 即 n - i*(i-1)/2 i*a需要该值为正且能被i整除for(inti2;i*(i-1)/2n;i)// 枚举序列长度i至少为2{intremn-i*(i-1)/2;// 计算去掉01...(i-1)后的剩余值// rem i*a需要rem0保证首项a为正整数且rem能被i整除if(rem0rem%i0)// 如果rem为正且能被i整除则存在合法首项a rem/ians;// 找到一个满足条件的序列答案加1}coutansendl;// 输出满足条件的连续正整数序列个数return0;}【运行结果】9 2