TopCoder SRM599: BigFatInteger

\( A = {p_1}^{q1} \times {p_2}^{q2} \times ... \times {p_n}^{qn} \)
\( A^B = {p_1}^{q1 * B} \times {p_2}^{q2 * B} \times ... \times {p_n}^{qn * B} \)
とする。

まず、X にAの素因数分をそれぞれ掛けて、 \( X = p_1 \times p_2 \times ... \times p_n \) を作る。
あとは素因数の指数が、\( \max_i{(qi * B)} \) を超えるまで X 自身を倍々に掛けていけばよい。
指数が超えた部分は、あとからなかったことにして辻褄を合わせることができるので気にする必要はない。

public class BigFatInteger {
    public int minOperations(long A, long B) {
        long primeNum = 0, maxPowNum = 0;
        for (long p = 2; p <= A; p++) {
            if (A % p == 0) {
                long powNum = 0;
                while (A % p == 0) {
                    A /= p;
                    powNum++;
                }
                maxPowNum = Math.Max(powNum * B, maxPowNum);
                primeNum++;
            }
        }
        int needPow = 0;
        long pow = 1;
        while (pow < maxPowNum) {
            needPow++;
            pow *= 2;
        }
        return (int)(primeNum + needPow);
    }
}