SRM628 Div1 Easy "DivisorsPower"

問題

TopCoder Statistics - Problem Statement

訳

ハリナは若い数学者だ。現在、彼女は正の整数を操る関数hについて興味を持ち勉強している。

d(n)をnの正の約数の数とする。関数hはh(n) = n^d(n)と定義される。言い換えれば、h(n)はnをd(n)乗したものである。

例えば、6は1, 2, 3, 6によって割り切れるため、d(6) = 4である。よって、h(6) = 6^4 = 1296である。

ハリナは関数hがどのようなものかを既に把握している。今彼女はhの逆関数を計算しようとしている。

あなたには、long nが与えられる。h(x) = nであるような、最小のxを返せ。そのようなxが存在しなければ-1を返せ。

制約

2 <= n <= 10^18

考えたこと

nがでけえなあ・・・

nが巨大な素数だったらどうしよう・・・
あ、その場合でも約数は1, nで２つできるから、最悪２乗されるからxは2～10^9の範囲なのか。じゃあxの約数の数え上げはできると。

よし、まず何乗してnになったかを決め打ちしてしまおう。2^60 > 10^18なので、2～60乗を試せばよい。それで2～10^9の範囲を二分探索でおｋ。

↓

WA

↓

Oh... Overflow...

そっかぁ・・・掛け算してnになるか試すんじゃなくて、nを割ってって1になるかを試せばオーバーフローしないのかぁ

ソースコード

class DivisorsPower {
public:

    long long findArgument(long long n) {
        // 60->2乗をためす
        for (int p = 60; p >= 2; p--) {

            // 二分探索
            int r = (int)1e9 + 1;
            int l = 1;
            while (l < r) {
                bool ok = true;
                int m = (r + l) / 2;
                long long t = n;
                for (int i = 0; i < p; i++) {
                    if (t % m != 0) ok = false;
                    t /= m;
                }
                if (ok && t == 1) {
                    int cnt = 0;

                    // 約数数え上げ
                    for (int d = 1; d * d <= m; d++) {
                        if (m % d == 0) {
                            if (m / d == d) {
                                cnt += 1;
                            }
                            else {
                                cnt += 2;
                            }
                        }
                    }
                    if (cnt == p) return m;
                }
                if (t == 0) {
                    r = m;
                }
                else {
                    l = m + 1;
                }
            }
        }
        
        return -1;
    }
};