一般論

二重ループでも、$O(n^2)$ になるとは限らない。

for (int d = 1; d <= N; d++) { // d は間隔（公差）
    for (int x = d; x <= N; x += d) { // d, 2d, 3d, ... (N を超えない範囲) 
        // floor(N/d) 回呼ばれる
    }
}

全体のループ回数はだいたい $\displaystyle n + \frac{n}{2} + \frac{n}{3} + \cdots \frac{n}{n} = n(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}) = O(n \log n)$

調和級数ループが出てくるところ

• $0 < d, x \leq M,\ d \mid x$ を満たす $(d, x)$ の全列挙（計算量は $O(M \log M)$）

  • $d \mid x$ のとき、ある $k$ が存在して $x = dk$ と書けるので、$dk \leq M$ を満たす $(d, k)$ 全列挙と同じ話
  • 劣化エラトステネスの篩でも出てくる

• $x, y\geq 1,\ xy \leq M$ を満たす $(x,y)$ の全列挙（計算量は $O(M \log M)$）

• Rust での実装

問題例

• ABC393 E - GCD of Subset
• ABC356 E - Max/Min
• ABC331 E - Set Meal （別解）
• ABC385 C - Illuminate Buildings
• ARC197 C - Removal of Multiples
• 約数の個数テーブルの作成

調和級数

$H_n = 1 + 1/2 + \cdots 1/n$ を調和数という。

$H_n = O(\log n)$ である。