数論
01 / 共通の仕組み
多くの問題は数論的な背骨を隠している。入力に潜む割り切り / 法 / 乗法の構造を見抜けば、 O(N) のループは O(log N) や O(N log log N) へと縮む。 古典的なサブパターンは 3 つ:ユークリッドの互除法での GCD、 指数を半分にしながらべき乗を取る冪剰余、合成数を一気にふるい落とす素数篩。
01 / 一文での本質
1 回の共有スキャンで、すべての素数の倍数を歩く。合成数は最小素因子によって最初にマークされる; 素数は生き残って自分の倍数をマークする。表全体が O(N log log N) で埋まる —— 各合成数の被マーク回数は償却で O(log log N)、約数ごとに 1 回ではない。
問題N 以下のすべての素数を求めるN20
まず 2 から 20 までのすべての数を素数と仮定。各生存素数の倍数を辿って合成数をマークしていく。
ステップ
0 / 16
現素数
—
素数の数
—
N
20
0 / 16
02 / パターンの骨格
# エラトステネスの篩is_prime[0..N] ← [True] * (N+1)is_prime[0] = is_prime[1] ← Falsefor p in 2..⌊√N⌋:if is_prime[p]:for m in p*p..N step p: # p² から開始 — それ未満の倍数は既にマーク済みis_prime[m] ← Falsereturn [i for i in 2..N if is_prime[i]]
03 / このパターンを使うべき合図
「N 以下のすべての素数」
最も典型的な用途 — LC 204。各数ごとに試し割りするより log 倍速く、 ウィルソンの定理よりはるかに速い。
N がメモリに収まるなら答えはこれ。「各数の最小素因子」
線形篩のバリエーション:走査中、最初に
m を合成数とマークした素数が その最小素因子になる。真偽値の代わりに spf[m] を保存すれば、 任意の数を O(log m) で素因数分解できる。「大量の数の素因数分解」
まず
spf[] を O(N log log N) で前計算し、各クエリは spf[n] で繰り返し割って O(log n) で分解する。 値域 N、Q クエリで合計 O(N log log N + Q log N)。「ある性質を持つ素数の和 / 個数」
問題が「N 以下の素数を列挙する」に帰着するとき — 素数の個数、素数番目の和、 k で割った余りが r の素数。一度篩って、フィルタする。各候補を独立に試し割りしてはいけない。
04 / よくある落とし穴
i.
内側のループを
p*p ではなく p*2 から始める。無駄な作業 —
p*p 未満の p の倍数はすべてより小さい素因子を持ち、 既にマーク済み。p = 7 なら、14, 21, 28, 35, 42 を冗長に再マークしてしまう;49 以降になって初めて p は新たなマークに寄与する。 この最適化が複雑度の上界を締める鍵。ii.
篩を
O(N log log N) ではなく O(N log N) と思い込む。素朴な上界
Σ N/p, 素数 p ≤ N は調和級数のように見えるが、素数の逆数和は log log N + O(1)(メルテンスの定理)であって log N ではない。正しい上界を引用すること: 実用スケールで N log N よりかなり締まっている。iii.
外側のループの
p の上限のオフバイワン。外側は
p を ⌊√N⌋ を含めて回すべき —— 未満ではない。任意の合成数 m ≤ N は ≤ √m ≤ √N の素因子を持つので、√N より大きい素数は新たなマークに寄与しないが、N が完全平方数のときはp = √N 自身が必要。05 / LeetCode で練習
4 問。最初の 1 問は教科書的な篩;残りの 3 問は同じ前計算表(素数 / SPF)の下流応用 —— 因数分解、乗法的計数、GCD によるグルーピング。
— / どれをいつ使うか
GCD / LCM
問題の核が割り切りであるときに使う — 公約数、互いに素か、既約分数、
a · b / gcd(a, b) から LCM を導出。 ユークリッドの恒等式 gcd(a, b) = gcd(b, a % b) は 1 ステップごとに幾何級数で減る。ユークリッド · LC 1071 · LC 1979
冪剰余
巨大な n に対する
aⁿ mod M や素数を法とする乗法逆元が必要なときに使う。 指数を毎ステップ半分にし、n のビット並びでどの平方項が乗算されるかが決まる。O(log n)。指数の半減 · LC 50 · LC 372
素数篩
N 以下の素数(または最小素因子)を全て列挙するときに使う。 各素数 p の倍数を合成数として一気にマークする; 各合成数のマーク回数は償却 O(log log N)。
エラトステネス · LC 204 · LC 952