北大 acm 2853 Sequence Sum Possibilities 解题报告

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3448 Accepted: 2318

Description

Most positive integers may be written as a sum of a sequence of at least two consecutive positive integers. For instance,
6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4but 8 cannot be so written.

Write a program which will compute how many different ways an input number may be written as a sum of a sequence of at least two consecutive positive integers.

Input

The first line of input will contain the number of problem instances N on a line by itself, (1 ≤ N ≤ 1000) . This will be followed by N lines, one for each problem instance. Each problem line will have the problem number, a single space and the number to be written as a sequence of consecutive positive integers. The second number will be less than 231 (so will fit in a 32-bit integer).

Output

The output for each problem instance will be a single line containing the problem number, a single space and the number of ways the input number can be written as a sequence of consecutive positive integers.

Sample Input

71 62 93 84 18005 9876543216 9876543237 987654325

Sample Output

1 12 23 04 85 176 17 23

题意明确这里不重复 思路：等差数列的求和公式na1+n(n-1)d/2 式中的n为代码中的i，式中的a1为代码中的j

代码

#include <iostream>

using namespace std;

int main()
{
  long n,sum;
  long i,j,t,num,count,s;

  cin>>t;

  while(t--)
  {
    cin>>num;   
    cin>>n;   
    count=0;   

    for(i=1;;i++) //此处只为算出前i项和大于n的第一个数赋值为s
    {
      sum=i+i*(i-1)/2;
      if(sum>n)
      {
        s=i;
        break;
      }
    }   

    for(i=2;i<s;i++)
      for(j=(n/i)-1-i/2;j<=n/i-i/2+1;j++)
      {
        sum=i*j+i*(i-1)/2;     
        if(sum==n)
        {
          count++;
          break;
        }     

        if(sum>n)
          break;
      }

    cout<<num<<" "<<count<<endl;
  }

  return 0;
}