連載しょぼんコーダー 5 floor(N/i)を楽に列挙する方法

はじめに

正の整数 $N$ を固定します. $i \ge 1$ として, $\lfloor N/i \rfloor$ を考えることはよくあります. ここで $\lfloor x \rfloor$ は $x$ を超えない最大の整数です.

$1 \leq i \leq N$ を自由に動かすとき, $\lfloor N/i \rfloor$ のとりうる値の種類の数は $\lfloor\sqrt{4N+1}\rfloor -1 \simeq 2 \sqrt{N}$ です.（A055086 - OEIS）

これらの値をすべて列挙する方法で, かなり楽なものを見つけたので今回はこれを紹介します.

コード

まずはc++, pythonコードを見せます.

//CPP
#include <bits/stdc++.h>
using namespace std;

int main(){
    long long N;
    cin >> N;
    long long i = N;
    while (i > 0){
        long long v = N / i;
        long long j = N / (v+1);
        cout << v << endl;
        i = j;
    }
}

#PYTHON
N = int(input())
i = N
while i > 0:
    v = N // i
    j = N // (v+1)
    print(v)
    i = j

$\lfloor N/i \rfloor$ のとりうる値を小さい順に表示させています.

このとき, $\mathrm{i}$ は $\lfloor N/r \rfloor = \mathrm{v}$ となるような最大の値になって, $\mathrm{j}$ は $\lfloor N/r \rfloor = \mathrm{v}$ でなくなる最大の値です.

つまり, $(\mathrm{j}, \mathrm{i}$ ]という半開区間が $\lfloor N/r \rfloor = \mathrm{v}$ となるような $r$ の区間となります.

証明？

$i=N$ （すなわち $\lfloor \frac{N}{i} \rfloor=1$ ）のときはokです. $\mathrm{v}$ の次にとりうる値は, $\mathrm{v} + 1$ 以上です.
このとき, $\mathrm{v}+1 \leq \frac{N}{\mathrm{j}}$ すなわち $\mathrm{j} \leq \frac{N}{\mathrm{v}+1}$ が成り立ちます.
これを満たす $\mathrm{j}$ の最大値は $\lfloor \frac{N}{\mathrm{v}+1} \rfloor$ です.
よって, 帰納的に最大という条件が満たされます. $i=1$ のときは, $\mathrm{j} = 0$ となるのでプログラムが終了します.

例題

E - Fraction Floor Sum

正の整数 $N$ に対して, $\displaystyle \sum^{N}_{i=1} \left\lfloor \frac{N}{i} \right\rfloor$ を求める問題です.

この問題は平方分割で解くことができますが, 今のやり方で解いてみます. $\mathrm{i} - \mathrm{j}$ は, $\lfloor \frac{N}{r} \rfloor = \mathrm{v}$ となる $r$ の個数であることに注目します.
これは答えに $\mathrm{v} \times (\mathrm{i} - \mathrm{j})$ だけ寄与します.

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long N, i, j, v, ans;
    cin >> N;
    i = N;
    ans = 0;
    while (i > 0){
        v = N / i;
        j = N / (v+1);
        ans += v * (i-j);
        i = j;
    }
    cout << ans << endl;
}