floor(N/i) の商列挙

$\lfloor N / i \rfloor$ がとる値は $O(\sqrt{N})$ 種類しかなく、値が $q$ になる $i$ は $\lfloor N / (q + 1) \rfloor < i \le \lfloor N / q \rfloor$ の範囲にまとまります。

• floor_ranges(N): $l \le i < r$ のとき $\lfloor N / i \rfloor = q$ となる組 $(l, r, q)$ のリストを、 $l$ の小さい順に返す。区間は $1 \le i \le N$ をちょうど覆う。 $O(\sqrt{N})$

例（ $\sum_{i=1}^{N} \lfloor N / i \rfloor$）:

ans = sum((r - l) * q for l, r, q in floor_ranges(n))

コード

def floor_ranges(n):
    # [(l, r, q), ...]: l <= i < r の i について n // i == q（1 <= i <= n を q の値ごとに分ける）
    res = []
    l = 1
    while l <= n:
        q = n // l
        r = n // q + 1
        res.append((l, r, q))
        l = r
    return res