約数の個数を O(n^1/3) で求める - ペケンペイのブログ約数列挙は $O(\sqrt{n})$ 掛かるが、約数の個数を求めるだけなら $O(\sqrt[3]{n})$ でできる。 以下のページを参考にした。 codeforces.com まず $\sqrt[3]{n}$ 以下の素数を用いて $n$ を素因数分解する。 $$ n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} X $$ $p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ と $X$ は互いに素なので、約数の個数を $d(n)$ と書くことにすると、 $$ d(n)=d(p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r})d(X) $$ が成り立つ。そのため $d(X)$ を求めれば $d(n)$ も求まる。 $X$ は次のいずれかの形をしている。 $$ X=1, \qquad X=p, \qquad X
