TopCoder, Single Round Match 652, Division 1, Level 1 : ThePermutationGame

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13229&rd=16316

問題概要

　Division 2, Level 2 とほぼ同一．ただし，こちらは答えを として， を求める．
　

解法

　基本的な考え方は Division 2, Level 2 と同一で， 全ての数の最小公倍数を で割った余りが答えとなります．ただし，剰余を取った時点で GCD を計算できなくなるので，愚直に求めることはできません．工夫して計算する必要があります．
　最小公倍数 - Wikipedia を読むと，各数を素因数分解して，出現する素因数について，その指数が最も大きい指数を取ったものを全て掛け合わせたものが最小公倍数であることが分かります．従って， をそれぞれ素因数分解し，各素因数について最大の指数を求めてから，それらを掛け合わせることで問題を解くことができます．
　ある 1 つの値 に対する素因数分解は 時間なので， 全てを素因数分解するのにかかる時間は です．また，素因数の数は（全て 2 の場合が最大であることから） 個であり，出現する素因数は 以下なので，掛け合わせるのに掛かる時間は です．従って，全体は 時間で実行できます．

コード

using LL = long long;
template < typename T = int > using VT = vector< T >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define fst first
#define snd second

constexpr int MOD = 1000000007;

// 素因数分解 O( √N )
vector< long long > primeFactorization( long long N );

class ThePermutationGame
{
public:
	int findMin( int N )
	{
		map< LL, int > primes;

		REP( i, 2, N + 1 )
		{
			VT< LL > ps = primeFactorization( i );
			map< LL, int > counts;
			for_each( ALL( ps ), [&]( const LL p ){ ++counts[p]; } );

			FOR( c, counts )
			{
				primes[ c.fst ] = max( primes[ c.fst ], c.snd );
			}
		}

		LL res = 1;
		FOR( c, primes )
		{
			REP( i, c.snd )
			{
				( res *= c.fst ) %= MOD;
			}
		}
		return res;
	}
};