学步园

From: http://www.blker.com/?p=745

找到的讲的最细致的一篇博文。

不过文里面代码变量w声明类型应该是double，

#include <stdio.h>
#include <math.h>

int main(int argc, char* argv[])
{
	// 等差数列求和公式 Sum = n*aFirst + n*(n-2)/2;
	// Sum 为要拆分的整数，
	// n 为拆分后连续自然数个数
	// aFirst 为连续自然数中的第一位数

	int Sum, aFirst;
	int i,j;
	int k,m;
	double w;
	printf("请输入要分解的自然数Sum: ");
    scanf("%d",&Sum);

    for(i = 1; i <= Sum/2; i++)  //由于是连续自然数，所以首项必定不可能大于sum/2
    {
        aFirst = i;
        w = (2*aFirst-1) * (2*aFirst-1) + 8*Sum;
        k = (int)sqrt(w);
        m = k - 2*aFirst + 1;
		int intw=(int)w;
        if(k*k != intw)  // k是一个平方数
            continue;
        else if(m %2 !=0)  // m必须为偶数
            continue;
        else
        {
            printf("可以分解%d个连续自然数：/n",m/2);
           
			for(int j=1;j<=m/2;j++)
			{
				printf("%d ",i+j-1);
			}
            printf("/n");
        }
    }  

    return 0;
}

方法利用了等差数列的性质，输入的整数是等差数列的和，假如这个数列是所求结果，数列中元素的个数就是结果的元素个数。

-----------------------------------------------------------------------------------------粉葛先------------------------------------------------------------------------------------------------

下面这个方法看似更加简洁一些：

根据等差数列，求一个数列长度的上界，然后枚举数列长度，满足条件的输出即可。

from：http://hi.baidu.com/ken2008huang/blog/item/099abd09e365e6a92eddd4b4.html

#include <stdio.h>
#include <math.h>
int main()
{
    int t,inum,M,res,n;
    int i;
    scanf("%d",&t);
    for(t;t>0;t--)
    {
        scanf("%d%d",&inum,&M);
        res = 0 ;
        n = (int)sqrt((double)M*2);
        for(i=2;i<=n;i++)
        {
            if(M*2%i==0 && M*2/i+1-i>0 && (M*2/i+1-i)%2==0 )
            {
				//既然i已经算出，那么元素个数就是i，计算出来a，就知道整个数列是多少了
				double ddd=(2*M/i+1-i)/2;
				int a=(int)ddd;
				for(int j=0;j<i;j++)
				{
					printf("%d ",a+j);
				}
				printf("\n");
                res++;
            }
        }
        printf("%d %d\n",inum,res);
    }
    return 0;
}

--------------------------------

看这里：http://blog.csdn.net/kennyrose/article/details/6544518

这篇文章里写的比较明白。

用等差数列的时候，将公式写出来，然后满足那个公式的所有aFirst都是满足条件的。

整个算法的时间复杂度为O(n)。