解説:#14 Xth root

## 解説 まず$\sqrt[x]{N}$が整数になるような整数$x$としては$1$~$63$が考えられます。(2でも64したら$10^{18}$を超えてしまうので) $x = 1$~$63$それぞれについて$\sqrt[x]{N}$が整数になるかを判定します。 $x \ge 3$については簡単です。$\sqrt[x]{N} \le 10^6$なので$\sqrt[x]{N}$を全探索し、何乗かして$N$になるかを調べれば$O(N^{\frac{1}{3}} \log N)$で全部判定できます。 問題は$x = 2$です。つまり$N$が平方数かを判定しなければなりません。もちろん$\sqrt{N}$のオーダーかけていては多分間に合いません。 標準ライブラリにあるsqrt関数は平方根を求めることができます。戻り値は浮動小数点型なので切り捨てして整数にしてこの値を$a$とすると、$a^2=N$または$(a+1)^2=N \iff N$が平方数です。($(a + 1)^2$があるのは浮動小数点の誤差で$\sqrt{100}=9.9999999$->切り捨てで$a=9$みたいになる可能性が否定できないからです。 sqrt関数の計算量は不明ですが速そうなので通ります。 計算量保証がほしい場合は、$N$から$a$を求めるのに二分探索を使うことができます。任意の$b>0$について$b < \sqrt{N} \iff b^2 \lt N$だから$b$が$a$より小さいか大きいかは簡単に判定できるため二分探索で$a$を求めることができます。 実装例は以下の通りです。 ``` #include <bits/stdc++.h> int main() { long long n; scanf("%lld", &n); int res = 1; for (int i = 2; i <= 1000000; i++) { int64_t cur = i; int cnt = 1; while (cur != n) { if ((uint64_t) cur * (uint32_t) i / (uint32_t) i != (uint64_t) cur) break; // オーバーフロー対策 cur *= i; cnt++; } if (cur == n) res = std::max(res, cnt); } int sq = sqrt(n); if ((int64_t) sq * sq == n || (int64_t) (sq + 1) * (sq + 1) == n) res = std::max(res, 2); printf("%d\n", res); return 0; } ```