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で2つできるから、最悪2乗されるからxは2~10^9の範囲なのか。じゃあxの約数の数え上げはできると。
よし、まず何乗してnになったかを決め打ちしてしまおう。2^60 > 10^18なので、2~60乗を試せばよい。それで2~10^9の範囲を二分探索でおk。
↓
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; } };