数論
01 / 共通の仕組み
多くの問題は数論的な背骨を隠している。入力に潜む割り切り / 法 / 乗法の構造を見抜けば、 O(N) のループは O(log N) や O(N log log N) へと縮む。 古典的なサブパターンは 3 つ:ユークリッドの互除法での GCD、 指数を半分にしながらべき乗を取る冪剰余、合成数を一気にふるい落とす素数篩。
01 / 一文での本質
gcd(a, b) = gcd(b, a % b) —— a と b の両方を割り切る数は剰余も割り切る、だから値を小さな剰余で置き換えても答えは失われない。 ペアは毎ステップ幾何級数で縮み、log(min(a, b)) 回で終わる。LCM はその上に:a / gcd(a, b) · b。問題gcd(a, b) と lcm(a, b)a24b36
a = 24、b = 36 から開始。gcd(a, b) = gcd(b, a % b) を b = 0 になるまで適用する。
ステップ
0 / 5
a
24
b
36
gcd
—
lcm
—
0 / 5
02 / パターンの骨格
# ユークリッド GCD —— 右側が 0 になったら終了def gcd(a, b):while b ≠ 0:a, b ← b, a % b # 縮めるreturn a# LCM —— 先に割って溢れを防ぐdef lcm(a, b):return a / gcd(a, b) · b
03 / このパターンを使うべき合図
「最大公約数 / 公約数」
典型的な用途。LC 1071 ——「両方の文字列を割り切る最大の文字列」は 2 つの長さの GCD に帰着する。問題に「公約数」「共通因子」「両方を収める最大の単位」が出てきたら、 ユークリッドの出番。
「最小公倍数 / 周期」
a と b の両方で割り切れる最小数が必要なとき —— 同期周期、 繰り返し信号、「2 つのイベントが初めて揃う時刻」。まず
gcd を求め、 次に a / gcd · b —— 先に割れば a · b が溢れる場合でも 64 ビットに収まる。「分数は既約か / 互いに素か」
2 つの数が互いに素なのは
gcd(a, b) = 1 のとき。p/q の既約化は GCD 1 回と除算 2 回。有理数キーのハッシュ不変量、Stern–Brocot ツリーの巡回、Farey 隣接 —— すべてここに乗っている。「配列全体の GCD」
LC 1979。
{a₁, …, aₙ} の gcd は gcd(…gcd(gcd(a₁, a₂), a₃)…, aₙ) —— ペアごとに畳む。中間値は単調非増加、1 まで落ちたら早期終了できる; 総作業量は各回の縮約の和で抑えられる。04 / よくある落とし穴
i.
LCM を
a · b / gcd(a, b) として、先に割らない。先に掛けると 32 ビット整数で溢れる —— 64 ビットでも
a、b が 2³¹ に近いと危ない。必ず先に割る:a / gcd(a, b) · b。 この除算は厳密(gcd は a を割り切る)、 順序は安全で、中間値も最終答えを超えない。ii.
b == 0 の終了条件を忘れる。このガードが無いと、無限ループ(
a % 0 は未定義か例外)に陥るか、 最悪は最初のステップで b == 0 によるゼロ除算で落ちる。定義より gcd(a, 0) = a なので、ループからそのまま抜けさせれば良い。iii.
負数入力での結果の符号。
慣例として
gcd は非負。一部の言語の組み込み %(C など)は 被除数の符号に従うため、ガード無しの再帰では a が負に落ちることがある。入口で abs(a)、abs(b) を取るか、数学スタイルの剰余を使う。Python の % は除数の符号に従うのでそのまま使える;C/Java は使えない。05 / LeetCode で練習
4 問。最初の 3 つはユークリッド縮約の直接応用、最後の 1 つは Bézout の恒等式 ——gcd(a, b) は a·x + b·y と表せる最小の正整数 —— を使って実現可能性を判定する。
— / どれをいつ使うか
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