Appearance
数学・数え上げ
素数・約数
| アルゴリズム | 何ができるか | 計算量 |
|---|---|---|
| エラトステネスの篩 | N以下の素数列挙 | O(N log log N) |
| 素数判定 | 1つの整数の素数判定 | O(√N) |
| 素因数分解 | 素因数と指数を取得 | O(√N) |
| 約数列挙 | 整数の正の約数を昇順に列挙 | O(√N) |
| SPF（最小素因数） | 多数の整数を高速に素因数分解 | 前処理 O(N log log N) |
| 区間篩 | 区間[L, R]の素数判定 | 区間長などに依存 |
整数・数論
- GCD・LCM
- 拡張ユークリッドの互除法
- mod演算・逆元 | 商列挙 | 整数除算の商が等しい区間をまとめて処理 | O(√N) |
- 平方数判定 | 有理数（Rational） | 分数の厳密計算・四則演算・大小比較 | 演算ごとにGCD計算 |
組み合わせ・数え上げ
- 組み合わせ（nCr）
- 包除原理
- ベル数
- 調和級数