torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

 整数 N ( \leq 10^{ 18 } ) が与えられる.N素因数分解し,素因数を昇順に列挙した配列を return せよ.
 ただし,ヒントとして答えの偶数番目(0-based)の要素が全て与えられる.正確には,配列 primes が与えられ,primesi 番目の要素は答えとなる配列の 2i 番目の要素である.(従って,primes の要素数は,答えの配列の要素数M とすると \lfloor \frac{ M + 1 }{ 2 } \rfloor である)

解法

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

コード

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;
	}
};