きままにものづくり

日々の気付いたことなんかを書いてます。

SRM628Div1Easy

問題

割れる数を求める関数dを用いて h(x) = x^{d(n)}となる関数hを定義する。h(x)の値n( n \leq 10^{18})からxを求めよ。

解法

nの値が大きいので、xを全探索して答えを見つけることはできない。d(n)の値は十分小さいので、この値について全探索を行う。
 c = floor(\sqrt[m]{n} + 0.5)を計算し、 n = c^{m} \land m = d(c)となることを確認する。
 d(c)の計算は O(\sqrt{c})となる。

計算量

 O(log(n)*\sqrt[4]{n})

コード