pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

約数の個数を 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=p^2, \qquad X=pq $$

ここで $p$, $q$ は素数。$X$ の形さえ分かれば $d(X)$ が求まるので、$X$ の形を調べよう。

もし $X=pqr$ と表せたとすると $p, q, r \gt \sqrt[3]{n}$ なので $X=pqr \gt n$ だがそんなことはありえない。

X=1 の判定

X と 1 を比較すればいい。

X=p の判定

素数判定法を使えばいい。$O(\sqrt{n})$ の愚直な方法を使っては意味が無いので、Miller-Rabin 法を使う。

X=p2 の判定

$X$ が平方数であるか判定すればいい。平方数判定は sqrt を使えば楽。二分探索でも判定可能。

X=pq の判定

上記 3 ケースに該当しなければ、このケースに該当する。

Miller-Rabin 法を使うので直接これを問われる可能性は低いけど、これを使って強引に通すことは出来るかも。 $O(\sqrt[4]{n})$ でもできるらしいので考えたけど、rho 法を使った方法しか思いつかない。