ごり〜

こんばんは
高校数学ぐらいの内容ですが、整理していたらいくつか気づきがあったので記します
唐突ですが、「 $1$ から $N$ までの $n$ について、 $n$ の約数の個数の総和」をどう求めるか？を考えていきたいと思います
$N$ の大きさとしては $N \le 10^{12}$ ぐらいのを高速に求めたいです

なお、この記事で約数の個数とは、正の約数の個数を指します
出てくるグラフも $x \gt 0$ を定義域としています
ご了承ください

復習

約数

整数 $N$ の約数とは、 $N$ を割り切ることのできる整数です
以下、例として $1$ から $10$ までの $n$ について、 $n$ の約数を集合で表します

$1$ の約数： $\lbrace 1 \rbrace$
$2$ の約数： $\lbrace 1,2 \rbrace$
$3$ の約数： $\lbrace 1,3 \rbrace$
$4$ の約数： $\lbrace 1,2,4 \rbrace$
$5$ の約数： $\lbrace 1,5 \rbrace$
$6$ の約数： $\lbrace 1,2,3,6 \rbrace$
$7$ の約数： $\lbrace 1,7 \rbrace$
$8$ の約数： $\lbrace 1,2,4,8 \rbrace$
$9$ の約数： $\lbrace 1,3,9 \rbrace$
$10$ の約数： $\lbrace 1,2,5,10 \rbrace$

約数の個数

約数の個数に注目します。一般的な特徴は以下のようになります

1の場合

$1$ の $1$ 個だけです。

素数の場合

$n$ が素数の場合、約数は $1$ と $n$ 自身のちょうど $2$ 個です。

合成数の場合

$n$ が合成数の場合、約数は $1$ と $n$ の他にも $1$ 個以上存在します。
特に、 $n$ が平方数の場合は奇数個、そうでない場合は偶数個となります。

一般の場合

$n$ を素因数分解した結果が $p_1^{q_1} p_2^{q_2}\cdots p_k^{q_k}$ ( $p_i$ は素数)として、 $n$ の約数の個数は $(q_1 + 1)(q_2 + 1)\cdots(q_k + 1)$ となります
これを題材にした出題も、ときどき出てくるイメージなので忘れないようにしたいですね！ (今日は使いません)

(おまけ) 高度合成数

約数の個数に触れたので高度合成数というものにも軽く触れておきます。
約数の個数が多いやつは高度合成数と呼ばれて、こんな感じです
高度合成数の一覧 | アルゴ式この辺はキラーケースになることが多いです

反比例のグラフに乗る

$n$ の約数は、反比例のグラフ $y=\frac{n}{x}$ に乗ります。
$y=\frac{n}{x}$ を通る格子点の $x$ 座標を列挙すると(または $y$ 座標でも同じ)、 $n$ の約数に一致します。
下の図1では、 $n=6$ の例で、格子点の $x$ 座標は $1,2,3,6$ となり、 $6$ の約数と一致します。

特に個数に関しても、 $n$ の約数の個数は、 $y=\frac{n}{x}$ を通る格子点の個数に一致する
というのも、個人的には忘れがち/ 見逃しがちな言い換えな気がします
例えば、 $6$ の約数は $4$ 個 ⇔ $y=\frac{6}{x}$ を通る格子点は $4$ 個
です

本題

「 $1$ から $N$ までの $n$ について、 $n$ の約数の個数の総和」 を求めたいのですが、図にすると以下の図2の赤線の部分 (赤ドットの数)を数えたいです。

理由としては、以下の図3を見てほしいのですが、 $1$ から $N$ までの $n$ について、先ほどの $y=\frac{n}{x}$ のグラフを重ねていくと、 $N$ より内側の格子点をすべてもれなくカバーしていることがわかります (図では $N=6$ )

つまり、「 $1$ から $N$ までの $n$ について、 $n$ の約数の個数の総和」 とは、 $y=\frac{N}{x}$ のグラフの内側にある格子点の個数 と問題を言い換えることができました。

Nが小さい場合

まず $N \le 10^{6}$ の場合を考えます。
この場合は、下の図4のように縦に数えるだけで良いです。

具体的には、 $n$ が $1$ から $N$ にいたるまで、 $\lfloor \frac{N}{n} \rfloor$ を足して行けば良いです　( $\lfloor x \rfloor$ は床関数、整数切り捨て)

さて、 $N$ が大きい場合はどうしましょう...？？？

Nが大きい場合

本題の本題です。 $N \le 10^{12}$ の場合は、先ほどの方法では計算時間は間に合わず、大部分が計算できてないように思われます。
ところが、不思議なことにあとちょっとの工夫で求まるようになります。
キーワードは $\sqrt{N}$ で分割する です！

個人的に一番わかりやすいアプローチはこれでした。
以下、図をABC230-E kyopro_friendsさんのユーザ解説より引用しています

図5 Nが大きい場合 (ABC230-E kyopro_friendsさんのユーザ解説より引用)

図5を左から①②③④とします。
① = ② + ③ - ④ ということで、①が求めたいもので、②③④を求めれば良いと言っています。
そして、②と③は「斜めに折り返すと等しい」と書いてあります。
$y=\frac{N}{x}$ は $x$ と $y$ が対称な形をしており、 $x=y=\sqrt{N}$ がちょうど $x$ と $y$ が等しい部分になります。
そのため、②③のように $\sqrt{N}$ で分割すると、漏れなく①の領域をカバーできます。しかも、対称なので、②を求めて $2$ 倍するだけで③を足したことになります！
②の図は $N$ が小さい場合のように縦に足していき、 $M=\lfloor\sqrt{N}\rfloor$ として、 $1$ から $M$ までで打ち切れば良さそうですね。
最後に、ダブルカウントしている領域は④の部分だけになるので、ここは単に $M^{2}$ を引けば良いです。
これで $N$ が大きい場合についても、「 $1$ から $N$ までの $n$ について、 $n$ の約数の個数の総和」を求めることができました！

めでたし！

おまけ

問題リンク

ABC230-E
- この記事の説明で使わせていただきました
- 約数という言葉は出てこないですが、この記事でそのまま求めた内容です
ABC414-E
- 問題を整理すると、約数の個数の総和が欲しくなります