解题思路:
1、暴力
暴力方法就是每次枚举起点和终点,统计起点和终点直接的和是否满足即可,代码如下:
#include <iostream> using namespace std; int sum, m; int main() { while (cin >> m) { for (int i = 1, j; 2 * i < m; ++i) { sum = 0; for (j = i; j < m; ++j) { sum += j; if (sum >= m) break; } if (sum == m) cout << i << " " << j << endl; } cout << endl; } return 0; }
2、前缀和
从暴力的基础上修改,暴力的内层循环使用前缀和简化
#include<cstdio> using namespace std; int s[2000005], m; int main() { while(~scanf("%d", &m)) { for(int i = 1; i <= m; i++) s[i] = s[i - 1] + i; for(int i = 1; i < m; i++) for(int j = i + 1; s[j] - s[i - 1] <= m; j++) if(s[j] - s[i - 1] == m) printf("%d %d\n", i, j); puts(""); } return 0; }
3、数学
设首项为L,末项为R,那么sum(L,R)=(L+R)(R-L+1)/2=M
即(L+R)(R-L+1)=2M
可以把2M分解成两个数之积,假设分成了两个数i,j,且i<j
可以列一个二元一次方程组R-L+1=i,L+R=j
解得L=(j-i+1)/2, R=(i+j-1)/2
当i,j一奇一偶时,L,R才有自然数解.
不过有一种特殊情况,就是L=R的情况,这种情况是不允许的
即(j-i+1)/2≠(i+j-1)/2,解得i≠1
#include<cstdio> #include<cmath> using namespace std; int main() { int m; while (~scanf("%d", &m)) { for(int i = sqrt(2 * m); i>1; i--) //枚举i(注意是i>1而不是i>=1) if(2 * m % i == 0 && (i + 2*m/i) % 2) { //如果j是整数而且与i一奇一偶 int j = 2 * m / i; printf("%d %d\n", (j - i + 1) / 2, (i + j - 1) / 2);//输出答案 } puts(""); } return 0; }
0.0分
9 人评分
C二级辅导-同因查找 (C语言代码)浏览:555 |
简单的a+b (C语言代码)浏览:489 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:584 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:575 |
蛇行矩阵 (C语言代码)浏览:743 |
【亲和数】 (C语言代码)浏览:501 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:574 |
众数问题 (C语言代码)浏览:822 |
【亲和数】 (C语言代码)浏览:597 |
1128题解(返回值为数组的情况)浏览:451 |