paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 最大公約数

最大公約数 (paizaランク C 相当)

JavaScriptで解いてみました。
素直にAかBの小さい方から１へ向けて、ループで繰り返して最大公約数を探すと、1 ≦ A , B ≦ 10 ^ 10なので、タイムオーバーになります。

ユークリッドの互除法を使います。

１、aをbで割り、余りrを求め、
２、aにbを代入して、bにrを代入して、
３、またaをbで割り、余りrを求め、を繰り返し、
４、rが0になった時のbが最大公約数です。

ユークリッド互除法のイメージは、次のとおりです。a>bの自然数、aとbの最大公約数nとします。ダルマ落としのダルマのようにaとbを積み上げますが、体のパーツの大きさが最大公約数nで積み上げます。大きい方aを小さい方bで、スコーン！と、ダルマ落とししていきます。bより小さくなった元aのダルマの方が余りrになりますが、またこのrで、大きい方(ひとつ前のb)をまたスコーン！とダルマ落としします。繰り返すと最終的に、ダルマの顔が１つしか残らないのですが、それが求める最大公約数nです。

ちなみに、お互いダルマ落としで、スコーン!と体を除いていきますが、このイメージから、互いに除く方法ということで、互除法と言います。割り算のことを除法とも言いますが、この除くイメージからきています。ユークリッドさんが発見したので、ユークリッドの互除法です。

このユークリッドの互除法のイメージが浮かばない人は、スマホアプリのアルゴリズム図鑑が、イメージ図に動きをつけて、無料で解説しているので、わかりやすくてオススメです。

解答例

素直にユークリッド互除法を適用します。余りをrとしました。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

let [a, b] = lines[0].split(" ").map(Number);
let r = 1;//aをbで除いた余りa%b,while(r>0)なので初期値1とした。
while (r > 0) {　//余りrが0になるまで(ダルマの頭１つになるまで)
    r = a % b;//除法(aをbでダルマ落とし、残るのがr)
    if (r > 0) {
        [a, b] = [b, r];//落とされるダルマと落とすダルマを入れ替え
    }
}
console.log(b);//求める最大公約数

解答例

上記の解答のrを使わず、while(b>0),r=a%b,console.log(a)として、コードを短縮しました。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

let [a, b] = lines[0].split(" ").map(Number);

while (b > 0) { //b(余り)が0になるまで
    [a, b] = [b, a % b];//除法と代入をまとめた。
}
console.log(a);//求める最大公約数

解答例(Pythonの場合参考)

再帰関数を使うこともできます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [a, b] = lines[0].split(" ").map(Number);

//最大公約数を求める関数定義
let gcd = (a, b) => {
    if (b === 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
};

console.log(gcd(b, a % b));//関数実行して出力