78这个数可以表示为连续正整数的和 18+19+20+21,25+26+27。输入一个正整数 n(n<=10000),输出 m 行(n有m种表示法),每行是两个正整数a,b,表示a+(a+1)+...+b=n,对于多种表示法,a小的方案先输出。C++y语言 不用函数
时间: 2023-12-20 14:03:17 浏览: 177
以下是实现代码:
```c++
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = 0; // 表示方案数
for(int i = 1; i <= n; i++) {
int sum = i * (i + 1) / 2; // 计算 1~i 的和
if(sum > n) break; // 如果超过 n 则退出循环
if((n - sum) % (i + 1) == 0) { // 如果差能被 i+1 整除
int a = (n - sum) / (i + 1) + 1; // 计算 a
cout << a << " " << a + i << endl; // 输出答案
cnt++; // 方案数加 1
}
}
if(cnt == 0) cout << "NONE" << endl; // 如果没有方案,则输出 NONE
return 0;
}
```
代码思路:
首先,我们可以想到的是暴力枚举,对于每一个起点 i,向后枚举连续的正整数,计算它们的和是否等于 n,如果等于,则输出答案。但是这样的时间复杂度是 $O(n^2)$,不太理想。
我们可以换一种思路,考虑如何快速计算连续正整数的和。对于从 1 到 i 的连续正整数,它们的和可以用等差数列求和公式来计算,即 $sum = i \times (i+1) / 2$。
接下来,我们只需要枚举起点 i,计算出 1~i 的和 sum,然后判断差 n-sum 能否被 i+1 整除,如果能,则说明存在一组解。
最后,我们再统计一下方案数,如果方案数为 0,则输出 NONE。
注意,本题需要注意一些细节问题,例如:
- 如果 n 本身就是一个连续正整数的和,此时 a 应该为 n,而不是 1;
- 如果没有方案,则输出 NONE。
阅读全文