拡張ユークリッドの互除法 (旧)

ユークリッドの互除法

hogeちゃん

2022.10.26

ユークリッドの互除法メニュー【ユークリッドの互除法・3 つ以上の整数の最大公約数・最小公倍数・ax + by = c・拡張ユークリッドの互除法】

問題【STEP: 1】ユークリッドの互除法

Task

A , B の最大公約数 gcd(A , B) の値を 1 行で出力してね。

【STEP: 1】コード

  // 2 つの整数 A , B の最大公約数（gcd(A , B)）を高速に求めるアルゴリズム
reader.on('close', () => {
   const [A, B] = lines[0].split(' ').map(Number);
   let a = Math.max(A, B);  // A , B のうち大きい方
   let b = Math.min(A, B);  // A , B のうち小さい方
   while (a && b) {  // a と b の双方が true の間
      a %= b;  // 小さい方で大きい方を割り 大きい方をその余りで置き換え…
      [a, b] = [b, a];  // a, b の値を置換 (a %= b なので 値を入れ替える前は a < b)
   }
   console.log(a);
});

hogeちゃんの画像

2 つの整数 A , B の最大公約数（gcd(A , B)）を高速に求めるアルゴリズムをユークリッドの互除法って云うらしい。

問題【STEP: 2】3 つ以上の整数の最大公約数

Task

A_1 〜 A_N の最大公約数の値 gcd(A_1 〜 A_N) を出力してね。

【STEP: 2】コード

  // 3 つ以上の整数の最大公約数を求める演算 gcd(...gcd(gcd(gcd(a,b),c),d)...)
reader.on('close', () => {
   const N = Number(lines[0]);
   const A = [];  // N 個の整数
   for (let i = 1; i <= N; i++) {
      A.push(Number(lines[i])); 
   } 
   while (A.length >= 2) {  // A の要素数が 2 以上の間ユークリッドの互除法をループ
  // ここから ユークリッドの互除法
      let a = Math.max(A[0], A[1]);  // A[0], A[1] のうち大きい方
      let b = Math.min(A[0], A[1]);  // A[0], A[1] のうち小さい方
      while (a && b) {  // a と b の双方が true の間
         a %= b;  // 小さい方で大きい方をわり 大きい方をその余りで置き換え…
         [a, b] = [b, a];  // // a, b の値を置換
      }
  // ここまで
      A.splice(0, 2, a);  // 0 番目から 2 個の要素を削除し 0 番目に a を埋め込み
   }
   console.log(...A);
});

hogeちゃんの画像

A[0], A[1] の最大公約数 a を求め AからA[0], A[1]を削除し代わりに a を埋め込み。Aの要素数が 1 になるまで処理を繰り返し…。

問題【STEP: 3】最小公倍数

Task

A, B の最小公倍数 lcm(A,B) の値を出力してね。

【STEP: 3】コード

  // lcm(A,B) = A×B/gcd(A,B) = 最小公倍数
reader.on('close', () => {
   const [A, B] = lines[0].split(' ').map(Number);
  // ここから ユークリッドの互除法
   let a = Math.max(A, B);
   let b = Math.min(A, B);
   while (a && b) {
      a %= b;
      [a, b] = [b, a];
   }
  // ここまで
   console.log(A * B / a);  // 最小公倍数 = 元の値を乗算し 最大公約数で 除算
});

hogeちゃんの画像

A, B の最小公倍数…。

ユークリッドの互除法で最大公約数 a を求める。
A ✕ B ÷ a = 最小公倍数となる。

問題【STEP: 4】ax + by = c

Task

x または y が 1 であるような x + By = C の整数解 x , y の値を出力してね。

【STEP: 4】コード

  // Ax + By = C の整数解 x , y の値を出力
reader.on('close', () => {
   const [A, B, C] = lines[0].split(' ').map(Number);
   let [x, y] = [0, 0];
   switch (A > B) {
   case true:
      [x, y] = [1, -parseInt(A / B)];
      break;
   case false:
      [x, y] = [-parseInt(B / A), 1];
      break;
   }
   console.log(x, y);
});

hogeちゃんの画像

x または y が 1 であるような解の組の値を出力なのでこれでいいのかな??

問題【FINAL】拡張ユークリッドの互除法

Task

Ax + By = gcd(A , B) の整数解 x , y の値を出力してね。

【FINAL】コード

reader.on('close', () => {
   let [a, b] = lines[0].split(' ').map(Number);
   let [x, y] = [1, 0];
   let [nx, ny] = [0, 1];
   while (a % b) {
      let tmpx = x - parseInt(a / b) * nx;
      let tmpy = y - parseInt(a / b) * ny;
      a %= b;
      [a, b] = [b, a];
      [x, y] = [nx, ny];
      [nx, ny] = [tmpx, tmpy];
   }
   console.log(nx, ny);
});

hogeちゃんの画像

色々なサイトの解説も参照しながら試行錯誤しているうちにこんな感じになりました。正直イマイチ理解できていない。まだまだですね。(^_^;

【FINAL】コード 2

reader.on('close', () => {
   function extgcd(a, b) {
      if (b) {
         const [c, y, x] = extgcd(b, a % b);
         let yy = y;
         yy -= Math.floor(a / b) * x;
         return [c, x, yy];
      }
      return [a, 1, 0];
   }
   const [A, B] = lines[0].split(' ').map(Number);
   const [C, X, Y] = extgcd(A, B);
   console.log(X, Y);
});

hogeちゃんの画像

問題文の疑似コードを参照。

コメント