No.456

単純な二分探索だと, 階乗と $\log$ の計算が重く, イテレーション数も多いため TLE となる.

そこで, 元の式

$$n^a \log^b n = t$$

の両辺を $1/b$ 乗して,

$$n^{a/b} \log n = t^{1/b}$$

となり, $n^{a/b} = x$ とおくと,

$$x \log x^{b/a} = t^{1/b} \\ x \log x = (a/b)t^{1/b}$$

となる. 右辺は定数なので, $\log$ 一回に減らせる.

また, 二分探索ではなくニュートン法を使うことでイテレーション数を減らすことができる.