最大公約数とユークリッドの互除法
最大公約数(GCD, Greatest Common Divisor)は、両方の数を割り切る最大の数です。約数を一つずつ求めて比べる代わりに、ユークリッドの互除法でO(log)に速く求めます。最小公倍数(LCM)はGCDさえ分かれば即座に計算できます。
核心の一行: 「大きい数を剰余に置き換えて縮める」。 2つの数が剰余演算で小さくなり、剰余が0になった瞬間が答えです。
核心の性質
gcd(a, b) = gcd(b, a mod b)
a を b で割った剰余で問題を縮め、b が0になればそのときの a が最大公約数です。
なぜ成り立つか？ a = q·b + r と書くと、a と b の公約数は b と r(= a mod b) の公約数とちょうど一致します(片方を割れば他方も割る)。だから (a, b) を (b, a mod b) に置き換えても最大公約数が保たれます。
動作原理
ステップ1. b が0なら a が最大公約数です(終了)。
ステップ2. そうでなければ gcd(b, a mod b) に縮めて再帰(またはループ)します。
ステップ3. 剰余が0になるまで繰り返すと、割る数がGCDとして残ります。
AlgoNoteの可視化は、2つの数が剰余演算でどう縮むかをステップごとに示します。
LCMはGCDから
lcm(a, b) = a / gcd(a, b) × b
積 a × b をGCDで割った値です。ただし a × b を先に掛けると大きな数でオーバーフローし得るので、a / gcd × b の順で先に割るのが安全です。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(log(min(a, b))) |
| 空間 | O(1)(反復実装) |
剰余演算が毎ステップ値を速く縮めるので対数時間です。
例で追ってみる
gcd(48, 18):
- •gcd(48, 18) → 48 mod 18 = 12 → gcd(18, 12)
- •gcd(18, 12) → 18 mod 12 = 6 → gcd(12, 6)
- •gcd(12, 6) → 12 mod 6 = 0 → gcd(6, 0) = 6
よってGCDは6、lcm(48,18) = 48 / 6 × 18 = 144 です。
よくあるミス
- •LCMのオーバーフロー:
a × bを先に掛けると型の範囲を超え得ます。先に割りましょう。 - •0の処理:
gcd(a, 0) = aの規則を抜かすと終了条件が壊れます。 - •負の入力: 通常は絶対値を取って扱います。
AlgoNoteで直接確認しましょう
大きい数が剰余演算で小さくなり最大公約数に到達する過程をAlgoNoteでステップごとに確認できます。