na_o_ysのブログ

プログラミングのメモ

SRM 628 Div1 Easy, DivisorsPower

問題

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;
    }
};

備考

本番では  x = 1\dots(10^{18})^{1/4} について  h(x) を求めてハッシュマップに保存,  d(x) = 2, 3 の場合だけ別処理, みたいなめんどくさいことをしてしまった.
75分まるまる使って AC.