hdu

http://acm.hdu.edu.cn/showproblem.php?pid=2058

求1-N多少个连续字段和等于M.

假设 从i开始长度为k的字段和等于M,那么 ( i+  i+k-1) * k/2=M即(2*i+k-1)*k==2M   那么 从k<= sqrt(2*M);

i=M/k-(k-1)/2.这样通过从大到小枚举k的长度,并同时计算i的值判断和是否等于M,输出即可.

注意从(2*i+k-1)*k==2M这个式子得出的是k<=sqrt(2*M)而不是i,这样是为了方便计算,并且从大到小枚举k,也保证输出是按顺序输出。

#include<stdio.h>
#include<math.h>
int main()
{
    int n,m,l,k;
    while(scanf("%d %d",&n,&m)!=EOF&&n||m)
    {
        l=(int)sqrt(double(2*m));
        while(l)
        {
            k=m/l-(l-1)/2;
            if(k*l+l*(l-1)/2==m)
                printf("[%d,%d]
",k,k+l-1);
            l--;
        }
        printf("
");
    }
    return 0;
}