TopCoder, Single Round Match 643, Division 1, Level 1 ( Division 2, Level 2 ) : TheKingsFactorization

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13594&rd=16086

問題概要

　整数 が与えられる． を素因数分解し，素因数を昇順に列挙した配列を return せよ．
　ただし，ヒントとして答えの偶数番目（0-based）の要素が全て与えられる．正確には，配列 が与えられ， の 番目の要素は答えとなる配列の 番目の要素である．（従って， の要素数は，答えの配列の要素数を とすると である）

解法

　まず，ふつーに素因数分解してしまうとだいたい TLE します． を上手く使って計算時間を減らす必要があります．
　さて，求めるべき配列の内半分程度は入力で与えられるので，計算しなければならないのは残りの半分です．その残りの半分とは， とおけば の素因数分解であると言えます．
　試し割りによる の素因数分解を考えます．ふつーに考えると， の素因子になり得る素数を全て試す必要があるように思えますが，実は，ある程度以上大きな数で「割ってみる」必要はありません．これを示すためには， の与えられ方に着目します．求めたい素因数分解を多重集合と考え，これを とします．このとき， を求められれば， は自動的に求まります．若干唐突ですが， は を超えません．この値を とすれば， の存在と， の与えられ方から， は 以上の素因子を 3 または 4 つ含みます（未知の素因子は配列の奇数番目にあるものなので，間に挟まれている素因子が一つあってこれは 以上）．従って， でなければなりません． より， を示せます．従って， 以下の素因子を取り出し終わったとき（除算代入し終わったとき）， の素因子は高々 1 つになっています．従って，必要があれば残っている を答えに加えるという処理をするだけで， の素因数分解が完了します．
　あとは， の素因数分解と を併合してソートすれば解ができあがります．

コード

using LL = long long;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define PB push_back

class TheKingsFactorization
{
public:
	vector<long long> getVector( long long N, vector<long long> primes )
	{
		N /= accumulate( ALL( primes ), 1LL, multiplies< LL >() );

		REP( i, 2, 1000000 + 1 )
		{
			while ( !( N % i ) )
			{
				N /= i;
				primes.PB( i );
			}
		}
		if ( 1 < N )
		{
			primes.PB( N );
		}

		sort( ALL( primes ) );
		return primes;
	}
};