SRM599: BigFatInteger2

\( A = 2^{a1} \times 3^{a2} \times ... \times p_n^{an} \)
\( C = 2^{c1} \times 3^{c2} \times ... \times p_n^{cn} \)
より
\( A^B = 2^{a1*B} \times 3^{a2*B} \times ... \times {p_n}^{an*B} \)
\( C^D = 2^{c1*D} \times 3^{c2*D} \times ... \times {p_n}^{cn*D} \)

のように素因数分解して、あとは指数部分を比較する。

public class BigFatInteger2 {
    Dictionary<long, int> Factorization(long x) {
        var dictionary = new Dictionary<long, int>();

        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                int pow = 0;
                while (x % i == 0) {
                    x /= i;
                    pow++;
                }
                dictionary[i] = pow;
            }
        }

        if (x > 1)
            dictionary[x] = 1;

        return dictionary;
    }

    public string isDivisible(long A, long B, long C, long D) {
        var factorA = Factorization(A);
        var factorC = Factorization(C);

        foreach (var p in factorC.Keys) {
            if (!factorA.ContainsKey(p))
                factorA[p] = 0;
            if (factorA[p] * B < factorC[p] * D)
                return "not divisible";
        }

        return "divisible";
    }
}