TopCoder SRM 599, Division 2, Level 2 : BigFatInteger2

概要

整数 A, B, C, D が与えられる。
を で割り切れるかどうか求めよ。

解法

x を y で割り切れる ⇔ x の素因数の集合 ⊇ y の素因数集合　です。
従って、y の素因数であって、x の素因数集合に含まれる個数よりも多いものが存在すれば割り切れません。

実装に於いては、A, C の冪乗を愚直に計算すると明らかにオーバーフローするのでうまくやる必要があります。
指数法則によれば、ある値を n 乗すると指数が n 倍になります。
従って、A を素因数分解して指数を B 倍すれば の素因数の集合に含まれる個数が分かります。
についても同様です。
この結果を使って、先程の条件を満たす素因数が存在するかを調べることができます。

コード

typedef long long LL;

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

#define fst first
#define snd second

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

class BigFatInteger2
{
public:
	string isDivisible( int A, int B, int C, int D )
	{
		vector<LL> ab = primeFactorization( A );
		vector<LL> cd = primeFactorization( C );
		
		map<LL,LL> cntAB, cntCD;
		FOR( p, ab )
		{
			cntAB[p] += B;
		}
		FOR( p, cd )
		{
			cntCD[p] += D;
		}

		return any_of( ALL( cntCD ), 
			[&]( const pair<LL,LL> &p ){ return p.fst != 1 && cntAB[ p.fst ] < p.snd; } ) ? 
			"not divisible" : "divisible";
	}
};