paiza 問題集拡張ユークリッドの互除法 js

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

Task

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

【ユークリッドの互除法】コード 1/2

reader.on('close', () => {
   const gcd =(a, b) => {  // ユークリッドの互除法
      while (a && b) {  // a, b が 共に 0 でない間
         [a, b] = [Math.max(a, b), Math.min(a, b)];  // a > b になるように
         a = a % b;  // a を a mod b に置き換え
         [a, b] = [b, a];  // a と b を反転
      }
      return a;  // a を返す
   };
   const [A, B] = lines[0].split(' ').map(Number);
   console.log(gcd(A, B));
});

2 つの整数 A , B の最大公約数（gcd(A , B)）を高速に求めるアルゴリズムをユークリッドの互除法って云うらしい。とりあえず問題文の解説の流れに沿って記述してみました。

top

【ユークリッドの互除法】コード 2/2(再起関数)

reader.on('close', () => {
   const gcd = (a, b) => {
  // [a, b] = [Math.max(a, b), Math.min(a, b)];
      if (!b) {  // b が 0 になれば
         return a;  // a を返す
      }
      return gcd(b, a % b);  // gcd(a = b, b = a % b) を実行
   };
   const [A, B] = lines[0].split(' ').map(Number);
   console.log(gcd(A, B));  // gcd(A, B) の戻り値 a を出力
});

解答コード例参照。

例えば [a, b] = [5, 10] の場合

5 % 10 = 5なので

[a, b] = [b, a % b] = [5, 10]

[a, b] = [Math.max(a, b), Math.min(a, b)]; は実行しなくてもOK…。

top

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

Task

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

【3 つ以上の整数の最大公約数】コード 1/2

  // "3 つ以上の整数の最大公約数を求める演算 gcd(...gcd(gcd(gcd(a,b),c),d)...)"
reader.on('close', () => {
   const gcd = (a, b) => {
      if (!b) {
         return a;
      }
      return gcd(b, a % b);
   };
   const N = Number(lines[0]);
   const A = [];
   for (let i = 1; i <= N; i++) {
      A.push(Number(lines[i]));
   }
   for (let i = 1; i < N; i++) {
      A.splice(0, 2, gcd(A[0], A[1]));
   }
   console.log(...A);
});

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

top

【3 つ以上の整数の最大公約数】コード 2/2

  // "3 つ以上の整数の最大公約数を求める演算 gcd(...gcd(gcd(gcd(a,b),c),d)...)"
reader.on('close', () => {
   function gcd(a, b) {
      if (!b) {
         return a;
      }
      return gcd(b, a % b);
   }
   const N = Number(lines[0]);
   let G = Number(lines[1]);  // 最大公約数
   for (let i = 2; i <= N; i++) {  // i が 2 〜 N の間
      const A = Number(lines[i]);  // A の値を入力値で更新
      G = gcd(G, A);  // G の値をG, A の最大公約数で置き換え
   }
   console.log(G); // 全ての処理終了後の G を出力
});

入力値を A に代入して gcd(G, A) を i が N になるまで実行。

top

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

Task

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

【最小公倍数】コード 1/2

  // lcm(A,B) = A×B/gcd(A,B) = 最小公倍数
reader.on('close', () => {
   function gcd(a, b) {
      if (!b) {
         return a;
      }
      return gcd(b, a % b);
   }
   const [A, B] = lines[0].split(' ').map(Number);
   console.log(A * B / gcd(A, B));
});

A, B の最小公倍数…。

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

top

【最小公倍数】コード 2/2

  // lcm(A,B) = A×B/gcd(A,B) = 最小公倍数
  reader.on('close', () => {
     function lcm(a, b, c) {
        if (!b) {
           return c / a;
        }
        return lcm(b, a % b, c);
     }
     const [A, B] = lines[0].split(' ').map(Number);
     console.log(lcm(A, B, A * B));  // 最小公倍数 = 元の値を乗算し 最大公約数で 除算
  });

A, B の最小公倍数…。

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

top

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

Task

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

【ax + by = c】コード

reader.on('close', () => {
   const [A, B, C] = lines[0].split(' ').map(Number);
   let [x, y] = [0, 0];
   if (A % B === C) {
      x = 1;
      y = -(Math.floor(A / B));
   } else {
      x = -(Math.floor(B / A));
      y = 1;
   }
   console.log(x, y);
});

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

top

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

Task

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

【拡張ユークリッドの互除】コード 1/3

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

// 再起関数
   const extgcd = (a, b, x = 1, y = 0, nx = 0, ny = 1) => {     
       if (a % b === 0) {
          return [nx, ny];
       }
      const tx = x - Math.floor(a / b) * nx;
      const ty = y - Math.floor(a / b) * ny;
      return extgcd(b, a % b, nx, ny, tx, ty);
   };
   const [A, B] = lines[0].split(' ').map(Number);
   console.log(...extgcd(A, B));
});

色々なサイトの解説も参照しながら試行錯誤しているうちにこんな感じになりました。(^_^;

top

【拡張ユークリッドの互除】コード 2/3

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

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

top

【拡張ユークリッドの互除】コード 3/3

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

a, b, c を 0 以外の整数とする一次不定方程式 ax + by = c が整数解をもつための必要十分条件は c が gcd(a, b) で割り切れることである。

gcd(a, b) の値 (c) は出力しなくて良いので return [x, y]; に書き換えてみました。

top