北大 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

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}