ユークリッドの互除法 と 再帰 (最大公約数)

今回は paiza の「最大公約数」の問題に挑戦！
ユークリッドの互除法と再帰のテクニックを使った！

問題概要

• 整数 A , B が与えられる。
• A と B の最大公約数を求めて出力
• 条件：1 ≦ A , B ≦ 10 ^ 10
  
  
  

入力例：

3 6

出力例：

3

❌NG例：TLEの可能性

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [A, B] = lines[0].split(' ').map(Number);
    
    for (let i = Math.min(A, B); i > 0; i--) {
        if (A % i === 0 && B % i === 0) {
            // 最大公約数
            console.log(i);
            break;
        }
    }
});

ループ回数が最大で 10 ^ 10 になってしまう。

✅OK例：ユークリッド互除法 と 再帰

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [A, B] = lines[0].split(' ').map(Number);
    
    // ユークリッド互除法　
    function euculid (a, b) {
        if (b === 0) {
            return a; // 最大公約数
        } else {
            return euculid(b, a % b); // 再帰
        }
    }
    
    console.log(euculid(A, B));
});

🔍 このコードの流れ

• 標準入力を受け取る準備
  • readline を使って入力を1行ずつ受け取る
• 入力を配列 lines に保存
  • A B の1行が lines[0] に入る
• 入力終了時（close）に処理開始
  • lines[0] を分割して A, B を数値に変換
• ユークリッド互除法の関数を定義
  • euculid(a, b)
    • b === 0 なら a を返す（最大公約数）
    • そうでなければ euculid(b, a % b) を呼ぶ
• 最大公約数を計算
  • euculid(A, B) を実行
  • 再帰的に (a, b) が (b, a % b) に置き換わっていく
• 結果を出力
  • 最終的に返ってきた値を console.log で表示

※ 再帰：自分自身の関数を呼び出す（停止条件が必須）

💡 ユークリッドの互除法とは？

最大公約数（GCD）を「効率よく」求める方法。

ポイントは、

割り算の「余り」を使って、問題をどんどん小さくする

◎ 核となる考え方

A と B の最大公約数は、
B と A % B の最大公約数と等しい

なぜなら：

• A = B × 商 + 余り
• A と B の両方を割れる数は
  👉 必ず余りも割れる
• 逆に、B と余りを割れる数は
  👉 A も割れる

だから
gcd(A, B) = gcd(B, A % B)
が成り立つ。

具体例で見る（3 と 6）

1. gcd(6, 3)
2. 6 % 3 = 0
3. gcd(3, 0)

余りが 0 になった瞬間、答えは 3
👉 これが最大公約数

もう少し一般的な例（48 と 18）

gcd(48, 18)
→ gcd(18, 48 % 18 = 12)
→ gcd(12, 18 % 12 = 6)
→ gcd(6, 12 % 6 = 0)

余りが 0 になったので
答えは 6

なぜ速いのか？

• 毎回「余り」を取ることで、数が一気に小さくなる
• 半分以下になることも多い
• 繰り返し回数は多くても、log₂(max(A, B)) 回程度

だから計算量は
👉 O(log(max(A, B)))

10¹⁰ でも余裕で間に合う。

「再帰」と相性がいい理由

処理の流れがそのまま

gcd(a, b)
→ gcd(b, a % b)
→ gcd(…, …)
→ b === 0 で終了

という 「同じ形の処理の繰り返し」 だから。

function gcd(a, b) {
    if (b === 0) return a;
    return gcd(b, a % b);
}

• 「今の問題を、少し小さい同じ問題に変える」
• 再帰の典型パターン
  
  
  
  
  
  

📝まとめ

ユークリッドの互除法は、
「余りを使って、最大公約数の問題をどんどん小さくしていく方法」