连续自然数和-题解（C++代码）暴力、前缀和、数学三种方法

解题思路:
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;
}