学步园

Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.

For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.

20 10
50 30
0 0

[1,4]
[10,10]

[4,8]
[6,9]
[9,11]
[30,30]
看了网上的基本都是根据长度算出。先确定一段和sum＝m的最长的长度，要最长则起点从1开始，根据等差求和，len*(len+1)/2=m;放缩法则len^2<2*m,所以len=pow(2.0*m,0.5);现在根据长度确定起点L，根据等差求和公式，((len+L-1)+L)*len/2=m; =>  L=(2*m/len+1-len)/2; 判断时反代上式是否成立，是则输出[L,L+len-1。
正确代码：
#include<stdio.h>
#include<math.h>
int main()
{
    int n,m,l;
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        for(int len=(int)pow(2.0*m,0.5);len>=1;len--)
        {
            l=(2*m/len-len+1)/2;
            if(len*(len+2*l-1)/2==m)
            printf("[%d,%d]\n",l,l+len-1);
        }
        printf("\n");
    }
}



超时代码：

#include<stdio.h>
int main()
{
    int n,m,l,r,mid;
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        m=m<n?m:n;
        for(int i=1;i<m&&2*i+1<=m;i++)
        {
            l=i;r=m;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(2*m==mid*(mid+1)+i-i*i)
                {
                    printf("[%d,%d]\n",i,mid);break;
                }
                if(2*m<mid*(mid+1)+i-i*i) r=mid-1;
                if(2*m>mid*(mid+1)+i-i*i) l=mid+1;
            }
        }
        if(m<=n)
        printf("[%d,%d]\n",m,m);
        printf("\n");
    }
}