7E – The sum problem

开发者家乐技术 2022年11月9日

0 收藏 793 点赞 3,213 浏览 951 个字

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

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

Output

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.

Sample Input

20 10
50 30
0 0

Sample Output

[1,4]
[10,10][4,8]
[6,9]
[9,11]
[30,30]// 遍历所有子列

 #include<stdio.h>
 int main()
 {
     int n, m, i,j, t, flag;
     while(scanf("%d %d", &n, &m), !(n==&&m==))
     {
         for(i=;i<=n;i++)
         {
             flag=; t=;
             for(j=i;j<=n;j++)
             {
                 t+=j;
                 if(t==m)
                 { flag=; break; }
                 if(t>m) break;
             }
             if(flag) printf("[%d,%d]\n", i, j);
         }
         printf("\n");
     }
     return ;
 }

Time Limit Exceeded

// 老老实实算吧

 #include<stdio.h>
 #include<math.h>
 int main()
 {
     int n, m, i,j;
     while(scanf("%d %d", &n, &m), !(n==&&m==))
     {
         for(i=(int)sqrt(2.0*m);i>;i--)    // a1*n+n*(n-1)/2=(2*a1+(n-1))*n/2=m,
         {                                // 又a1>=1, 则n<sqrt(2*m).
             j=(*m/i-i+)/;            // a1=(2*m/n-n+1)/2
             if((*j+i-)*i/==m)
                 printf("[%d,%d]\n", j, i+j-);
         }
         printf("\n");
     }
     return ;
 }