問題

http://community.topcoder.com/stat?c=problem_statement&pm=13241&rd=16009
${ d(x) }$ は x の 1 以上 x 以下の約数の個数を表す. ${ h(x) = x^{d(x)} }$ とする. 与えられた整数 ${ n (2 \leq n \leq 10^{18}) }$ について, ${ h(x) = n }$ を満たす最小の x を求めよ. 存在しない場合は -1 を返す.

解法

$n \leq 10^{18}$ より, $d(x)$ の値は最大でも60である. $(2^{60} = 1.15 * 10^{18})$
$d(x) = 2\dots60$ について $x = n^{1/d(x)}$ を求め, $d(x), x$ の関係が条件を満たしているかどうか確かめれば良い.

解答

class DivisorsPower
{
public:
    long long findArgument (long long n)
    {
        for (int i = 60; i >= 2; i--) {
            ll x = pow(1.0*n, 1.0/i) + EPS;
            ll p = 1;
            repeat (i) p *= x;
            if (p == n && divisors(x) == i) return x;
        }
        return -1;
    }

    ll divisors(int n) {
        int cnt = 0;
        for (int i = 1; i*i <= n; i++) {
            if (n%i) continue;
            cnt++;
            if (i != n/i) cnt++;
        }
        return cnt;
    }
};