The sum problem

今天药忘吃喽~ 2022-08-01 00:30 301阅读 0赞

The sum problem

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18248 Accepted Submission(s): 5421

Problem Description

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

  1. 20 10
  2. 50 30
  3. 0 0

Sample Output

  1. [1,4]
  2. [10,10]
  4. [4,8]
  5. [6,9]
  6. [9,11]
  7. [30,30]

Author

8600

Source

校庆杯Warm Up

这是一个数学问题，直接求会超时！

利用数学公式中的等差公式就可以AC了！

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<iostream>
  4. using namespace std;
  5. /*
  6. M=Sn =a1*n+(n-1)n/2=a1*N+(N-1)N/2,
  7. 可得a1*N=M-(N-1)N/2;
  8. */
  9. int main()
  10. {
  11.     int n,m,sum,i;
  12.     while(cin>>n>>m&&(n+m))
  13.     {
  14.        // for(i=n;i>=1;i--)
  15.        for(i=(int)sqrt(2*m);i>=1;i--)
  16.         {
  17.             sum=m-i*(i-1)/2;
  18.             if(sum%i==0)
  19.             {
  20.                 cout<<"["<<sum/i<<","<<sum/i+i-1<<"]"<<endl;
  21.             }
  22.         }
  23.         cout<<endl;
  24.     }
  25. }

发表评论

表情：
评论列表 （有 0 条评论，301人围观）

还没有评论，来说两句吧...

相关阅读