きままにものづくり

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

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})$

コード