如何加速给定C++计数代码?附原循环实现与数学优化方案
C++计数代码加速优化方案
需求说明
需要统计满足1<=i<=j<=n且j-i<=a的整数对总数量,参数取值范围为1<=n<=1000000,0<=a<=1000000。
原始实现的问题
最初的版本采用双层嵌套循环逐一遍历所有可能的i、j组合做条件判断,时间复杂度为O(n²),当n、a取值较大时运算量会快速膨胀,运行效率极低。
原始代码如下:
#include <iostream> using namespace std; int main(){ int n, a, r = 0; cin>>n>>a; for(int i = 1; i <= n; i++){ int j = i; for(j; j <= n; j++){ if(j-i<=a){ r++; } } } cout<<r; }
优化思路
完全摒弃逐一枚举的循环逻辑,通过数学推导拆分场景直接计算结果,不需要遍历所有整数对,能把时间复杂度压到O(1),哪怕参数取到范围上限也能瞬时算出结果。
推导逻辑分场景判断:
- 当
a >= n时:所有满足1<=i<=j<=n的整数对自然符合j-i<=a的约束,总数量为等差数列和n*(n+1)/2。 - 当
a < n时:将所有有效整数对拆为两部分求和:- i的取值范围在
1 ~ n-a时,每个i可匹配的j范围为i ~ i+a,共a+1个合法值,这部分总对数为(n-a)*(a+1) - i的取值范围在
n-a+1 ~ n时,每个i可匹配的j范围为i ~ n,对应的合法j数量从a递减到0,这部分总对数为等差数列和a*(a+1)/2
- i的取值范围在
- 边界场景当
a=0时,每个i仅能匹配j=i一个值,总对数为n,可被上述通用公式完全覆盖。
实现时需要注意两个细节:
- 当n取到1e6时,计算得到的结果最大可达约5e11,远超32位int的取值上限,因此需要用
unsigned long long类型存储变量,避免整数溢出。 - 代码中单独判断a==0的分支为冗余逻辑,其计算结果可被n>a的通用分支完全覆盖,保留该分支仅为更直观展示边界场景,不影响计算正确性。
优化后代码
#include <iostream> using namespace std; int main(){ unsigned long long n, a, r = 0; cin>>n>>a; if(a==0){ r = n; } if(n<=a){ r = (n*(n+1))/2; } if(n>a){ r += (n-a)*(a+1) + (a*(a+1))/2; } cout<<r; }
内容的提问来源于stack exchange,提问作者ExonegeS
相关产品推荐
相关产品推荐

