[300]1934号最小公倍数

1934号最小公倍数

質問する

2つの自然数AとBについて、Aの倍数でありBの倍数である自然数をAとBの公倍数と呼ぶ.この公倍数の中で最小の数を最小公倍数と呼ぶ.例えば、6及び15の公倍数は30、60、90等であり、最小公倍数は30である.
2つの自然数AとBが与えられた場合、AとBの最小公倍数を求めるプログラムを作成してください.

入力

第1行は、試験例の個数T(1≦T≦1000)を与える.2行目からT行にまたがり、AとBが与えられる.(1 ≤ A, B ≤ 45,000)

しゅつりょく

1行目から、T行入力AとBの最小公倍数の順に1行ずつ出力します.

コピー例入力1

3
1 45000
6 10
13 17

コピー例出力1

45000
30
221

コード#コード#

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
3
1 45000
6 10
13 17
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const t = Number(input());

const gcd = (a, b) => {
  let res = 1;

  for (let i = 1; i <= Math.min(a, b); i++) {
    if (a % i === 0 && b % i === 0) res = i;
  }

  return res;
};

const lcm = (a, b) => {
  return (a * b) / gcd(a, b);
};

for (let i = 0; i < t; i++) {
  const [a, b] = input().split(' ').map(Number);
  console.log(lcm(a, b));
}

に答える

リファレンス

最大公約数の概念

の最大公約数をGCDと略す.

の最大承諾数は、2つのAとBの共通約数の中で最大の整数である.

の最大公約数を求める最も簡単な方法は、2からmin(A, B)をすべての整数に分割することである.

の最大公約数が1の2つの数を定数と呼ぶ.

最小公倍数概念

最小公倍数略称LCM.

の2つの数の最小公倍数は、2つの数の公倍数の中で最小の整数を指す.

最小公倍数は、以上で求めたGCD(最大公倍数)を適用して求めることができる.

頭数a、bの最大公倍数がgcdの場合、最小公倍数はlcm = gcd * (a/gcd) * (b/gcd)である.

これは

2a * b = gcd * lcmと同じ原理を利用している.

lcm = (a*b) / gcd.

function gcd(a, b) {
  let res = 1;

  for (let i = 1; i <= Math.min(a, b); i++) {
    if (a % i === 0 && b % i === 0) res = i;
  }

  return res;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(gcd(3, 12), lcm(3, 12)); // 3 12