商列挙（Floor Division Grouping）

floor(N / b) が同じ値になる区間をまとめて処理するテクニック。

通常O(N)かかる処理を、O(√N)に高速化できる場合がある。

特徴

項目	内容
用途	整数除算の商が等しい区間の列挙
計算量	O(√N)
空間計算量	O(1)（区間を保存しない場合）

重要な性質

整数Nを固定したとき、

floor(N / b)

の値は、bが増えるにつれて単調非増加となる。

同じ商になる除数は連続する区間を形成する。

例えばN=10の場合、

除数の区間 `[l, r)`	商
[1, 2)	10
[2, 3)	5
[3, 4)	3
[4, 6)	2
[6, 11)	1

区間の求め方

現在の左端をl、商をqとする。

cpp

ll q = n / l;
ll r = n / q + 1;

[l, r) のすべての整数bについて、

n / b == q

が成立する。

区間の要素数は r-l。

なぜO(√N)か

b <= √N の範囲は高々√N個。

b > √N の範囲では、商 floor(N/b) が√N未満になるため、異なる商の種類数も高々√N個。

したがって、区間の数はO(√N)となる。

実装

cpp


#pragma once
#include <cassert>
#include <climits>

template <class F>
void enumerate_quotients(long long n, F f) {
    assert(0 <= n && n < LLONG_MAX);
    for (long long l = 1; l <= n;) {
        long long q = n / l;
        long long r = n / q + 1;
        f(l, r, q);
        l = r;
    }
}

使用例

floor(N/b) の総和

cpp

ll ans = 0;
enumerate_quotients(n, [&](ll l, ll r, ll q) {
    ans += (r - l) * q;
});

計算量：O(√N)

※ 総和がlong longの範囲を超えないこと。

商と区間を列挙

cpp

enumerate_quotients(n, [&](ll l, ll r, ll q) {
    cout << l << " " << r << " " << q << '\n';
});

N=10の場合、

text

典型的な応用

floor(N/i) の総和
整数の組で i*j <= N を満たす組数
約数に関する総和
商を利用したDPや数え上げの高速化

注意点

除数bは1以上。
区間は半開区間 [l, r)。
r = n/q+1 とする。
商の値が変化する位置だけ処理する。
n+1 が整数型に収まる必要がある。
処理対象が floor(N/b) だけでなく、区間内のbにも依存する場合は、その区間の寄与を別途計算する。

商列挙（Floor Division Grouping） ​

特徴 ​

重要な性質 ​

区間の求め方 ​

なぜO(√N)か ​

実装 ​

使用例 ​

floor(N/b) の総和 ​

商と区間を列挙 ​

典型的な応用 ​

注意点 ​

関連 ​