SRM400 Div2 500

問題

p^qを考える。pは素数で、qは0より大きい整数。これをprime powerという。
もし、qが1より大きい場合は特にstrong prime powerという。
整数nが与えられるとき、このnがstrong prime powerならばそうなるpとqを返す。そうでなければ空の配列を返す。

考え方

「大きい数字はlogを取ってみる」ということで、n=p^qを式変形してp=10^(log10(n)/q)にする。
あとはqがそれほど大きくならない(60程度が最大)のがわかるので、qを2から60まで回す。
誤差も考えてpの前後についても調べて、整数に直したpが素数でかつ、p^q==nとなっていたらそれを返す。
p^q==nを確認する時、桁あふれを考え、long longだけでなくdoubleでも計算しておいて桁あふれしてるかどうかをチェックしないといけない。

反省

logじゃなくてもp==n^(1/q)で計算してもいい。