天天看點

poj-2140-Herd Sums- 數學規律-連續和為N的方案數

給出n,求   如果  一系列連續的數加起來能恰好得到n,為一種方案,求方案數

http://poj.org/problem?id=2140

設 a,a+1,a+2....a+k =n

那麼有 (k+1)*a+k*(k+1)/2=n;

(k+1)*(2*a+k)=2*n

如果(2*a+k),k+1是2*n因子;

我們隻需要找出 2*n的所有因子,并判斷 (2*a+k)能否被整除即可

#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <iostream>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm> 

using namespace std;

int main()
{

	int n;
	cin>>n;
	n=n*2;
	int ans=0;
	int i;
	int len=sqrt(double(n));
	for (i=1;i<=len;i++)
	{
		if (n%i==0)
		{
			if ((n/(i)-i+1)%2==0)
				ans++;
		}

	}
	printf("%d\n",ans); 
	return 0;  
}