HDU 1868 Consecutive sum 数学+枚举

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1868

题意

给出一个数n,求出这个数被分解成连续多个数之和的方案数

题解

连续多个数之和可以看成等差数列,得到公式:x(i+i+x-1)/2=n。这样我们可以枚举x,在根号n的复杂度下将问题求解

代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f
const int maxn=100005;
const int maxm=100005;

void solve()
{
ll x;
while(scanf("%lld",&x)!=EOF)
{
int ans=0;
for(int i=2;i*i<=2*x;i++)
{
if((2*x)%i) continue;
int tmp=2*x/i+1-i;
if(tmp%2) continue;
ans++;
}
printf("%d\n",ans);
}
}


int main()
{
freopen("input.txt","r",stdin);
solve();
return 0;
}