TopCoder SRM 599 Div1 Easy BigFatInteger

evima先生作問。

問題

自然数A, Bが与えられる。
最初X = 1で、Xに次の操作を繰り返し適用してX = A^Bとしたい。
操作の適用回数の最小値を求めよ。


1回の操作では以下のうちどれかを適用できる。

  • 好きな素数pを選んでX = p*Xとする
  • Xの好きな約数dを選んで、X = d*Xとする

制約条件

A, B≦10^6

方針

Aを素因数分解してA = p1^e1 * p2^e2 * … * pm^emとする。
まず全ての素因数が最低1回以上必要なのでm回操作が必要。


あとは指数は1, 2, 4, 8...と増やせるので、
2^kがmax(e1, e2, ..., em)以上になる最小のkが残りの操作に必要な回数。

ソースコード

class BigFatInteger {
	public:
	int minOperations(int A, int B) {
		int ans = 0, mx = 0;
		for(int i = 2; i * i <= A; i++) if(A % i == 0){
			int c = 0;
			for(; A % i == 0; A /= i) c++;
			
			mx = max(mx, 63 - __builtin_clzll((ll)c * B) + (__builtin_popcountll((ll)c * B) > 1));
			ans++;
		}
		if(A > 1) mx = max(mx, 31 - __builtin_clz(B) + (__builtin_popcountll(B) > 1)), ans++;
		return ans + mx;
	}
};