[UVa] 10290 - {Sum+=i++} to Reach N

題目網址: https://goo.gl/1vzl9i

題意:
(from luckycat)


解法:
假設一串有 m 項的數列首項為 a 滿足此 m 項的和為 n ，即是 (a+(a+m-1))*m/2 = n ，
則可以知道 2n = (2a + m -1)*m，分析得知 若 m 是偶數，則 (2a+m-1) 是奇數；反之，若 m 是奇數，則 (2a+m-1) 是偶數。
也就是說 若 2n 能夠拆成 某個奇數乘某個偶數，就能與一組數列和相等。
也就是找出 2n 有幾個 "奇數的因數"，也就是 n 有幾個 "奇數的因數"。
把 n 質因數分解，算出有幾個 奇數的因數 即是答案。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10290 - {Sum+=i++} to Reach N
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/11
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 30000005
	typedef long long ll;
	typedef vector<ll> VLL;
	// declarations
	ll n;
	bool isp[N];
	VLL pm;
	int ans;
	// functions
	void init( void )
	{
	pm.clear();
	clr( isp, true );
	isp[0] = isp[1] = false;
	for( ll i=2; i<=3e7; ++i ) if( isp[i] ) {
	pm.push_back(i);
	for( ll j=i*i; j<=3e7; j+=i )
	isp[j] = false;
	}
	}
	void solve( void )
	{
	if( n == 0 ) {
	ans = 0;
	return;
	}
	while( (n&1LL)==0LL ) n >>= 1;
	static int cnt;
	ans = 1;
	for( ll v : pm ) {
	if( v*v > n ) break;
	if( (n%v)==0LL ) {
	cnt = 1;
	while( (n%v)==0 ) {
	++cnt;
	n /= v;
	}
	ans *= cnt;
	}
	}
	if( n!=1LL ) ans *= 2;
	}
	// main function
	int main( void )
	{
	init();
	// input
	while( scanf( "%lld", &n )==1 ) {
	solve();
	// output
	printf( "%d\n", ans );
	}
	return 0;
	}

view raw 10290 - Sum i to Reach N.cpp hosted with ❤ by GitHub