连续自然数和 （C语言代码）

解题思路:

    方法1：由于数据比较小，所以可以用循环暴力破解即可。但是这一种方法效率比较低。如果数据比较大，则肯定超时。

    方法2：涉及到数论。使用等差数列公式，设第一项为：left, 最后一项为：right, 连续自然数和为M。

    使用等差数列求和可得：（left+right）*（right-left+1）=2*M

    再假设:k1=rihgt-left+l, k2=left+right  (k1<k2)

    此时把问题转化成了求两个整数k1,k2的乘积是2M。

    解方程可得： left=（k2-k1+1）/ 2  ,  right =（k1+k2-1）/ 2；

    值得注意的是因为left和right是自然数，这两个方程有解，当且仅当k1和k2一个奇数一个偶数；

    也就是说要满足： k1%2!=k2%2，对于k1从sqrt(2M)开始到1枚举即可。

    同时要注意left必须小于right。

    方法3：涉及到数论。使用等差数列公式，设第一项为：x, 最后一项为：x+n, 连续自然数和为M。

    使用等差数列求和可得：

        (2x + n)(n + 1)/2 =M  

    推导出 (2x + n)(n + 1) =2M，则n从sqrt(2M)开始到1枚举即可。那么x为多少呢？请看：

    ==>  2x + n = 2M / (n + 1)

    ==>  2x = 2M / (n + 1) - n

    ==>  x = ( 2M / (n + 1) - n ) /2

    又因为x为自然数数，所以，2M一定能被 (n + 1)整除，即2M % (n + 1)一定为零，

    另外，同理：(2M / (n + 1) - n ) % 2一定也为0。

参考代码:

//方法1：暴力破解
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
	int M,a;
	while(cin>>M)
	{		
		for(a=1;a<=M/2;a++)
		{		
			int sum=a;
			for(int b=a+1;;b++)
			{
				sum=sum+b;
				if(sum>M) 
					break;
				if(sum==M)
				{
					cout<<a<<" "<<b<<endl;
					break;
				}			
			}
		}
		cout<<endl;		
	}		
	return 0;
}

//方法2：用数论解决，效率高。如果数据比较大，不超过1e19，可以把int修改为 long long 即可。
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
	int M;
	while(cin>>M)
	{		
		M=2*M;
		for(int k1=sqrt(M);k1>=1;k1--)
		{
			if(M%k1==0)
			{
				int k2=M/k1;
				if(k1%2!=k2%2)
				{
					int left=(k2-k1+1)/2;
					int right=(k1+k2-1)/2;
					if(left<right)
						cout<<left<<" "<<right<<endl;
				}
			}
		} 
		cout<<endl;		
	}		
	return 0;
}

//方法3：用数论解决，效率高。如果数据比较大，不超过1e19，可以把int修改为 long long 即可。
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
	int M;
	while(cin>>M)
	{		
		M=2*M;
		for(int n=sqrt(M);n>=1;n--)
		{
			if( M%(n+1)==0 && ( M/(n+1)-n )%2==0 )
			{
				int x=(M/(n+1)-n)/2;
				if(x>0)
					cout<<x<<" "<<x+n<<endl;
			}
		}		
		cout<<endl;		
	}		
	return 0;
}