pekempeyのブログ

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

約数の個数の総和を O(√n) で求める

$n$ の約数の個数を $d(n)$ と書くとき、

$$ D(n) = d(1)+d(2)+ \cdots + d(n) $$

は $O(\sqrt{n})$ で求められる。


$n$ 以下の正整数で $i$ を約数に持つものは $\lfloor n/i \rfloor$ 個ある。このことから

$$ D(n) = \left\lfloor \frac{n}{1} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor $$

がいえる。$\lfloor n/i \rfloor$ の値はかなり重複するので、重複する部分をまとめて計算すると速そうである。

実際のところ $\lfloor n/i \rfloor$ が取りうる値は $O(\sqrt{n})$ 通りしかないので、計算量は $O(\sqrt{n})$ になる。 $$ \underbrace{ \left\lfloor \frac{n}{1} \right\rfloor,\, \left\lfloor \frac{n}{2} \right\rfloor,\, \ldots,\, \left\lfloor \frac{n}{\sqrt{n}} \right\rfloor}_{O(\sqrt{n})},\, \underbrace{ \left\lfloor \frac{n}{\sqrt{n}+1} \right\rfloor,\, \ldots,\, \left\lfloor \frac{n}{n - 1} \right\rfloor,\, \left\lfloor \frac{n}{n} \right\rfloor}_{O(\sqrt{n})} $$

前半は $O(\sqrt{n})$ 項しかないのだから $O(\sqrt{n})$ 通りしかなく、後半も $1$ から $\sqrt{n}$ の値しか取り得ないので $O(\sqrt{n})$ 通りしかない。

floor の値が等しいものを数え上げる際は、$\lfloor n/i \rfloor = v$ となる $i$ の範囲が $(\lfloor n/(v+1) \rfloor,\lfloor n/v \rfloor]$ になることを使う。


実装例。

約数の個数の総和 (O√n)

次のコードを用いて少なくとも n=106 までは正しい値を返すことを確認した。多分それ以降も大丈夫。

約数の個数の総和 | 検証コード

どちらかというと floor の性質の方が重要。