点検の周期の最大公約数と最小公倍数

数と計算
問題 07
やさしい
目安 11 分

2 台の機械の点検の周期の組が何組も与えられ、それぞれの最大公約数と最小公倍数を出す。1 から順に割って試さず、ユークリッドの互除法で求める練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

ある工場では、機械ごとに点検の周期が決まっています。周期が a 日の機械は、0 日目、a 日目、2a 日目、と a 日ごとに点検します。

2 台の機械の周期の組が T 組与えられます。それぞれの組 (a, b) について、次の 2 つを空白 1 つで区切って 1 行に出力してください。

a と b の最大公約数 (a と b の両方を割り切る正の整数のうち、最も大きい数)
a と b の最小公倍数 (a でも b でも割り切れる正の整数のうち、最も小さい数)。0 日目のあと、2 台を同じ日に点検するのは、この日数のあとになります

入力の形式

T
a_1 b_1
a_2 b_2
...
a_T b_T

1 行目に組の数 T、2 行目から T 行に、1 行に 1 組ずつ a_i と b_i が空白 1 つで区切られて並びます。

出力の形式

T 行を出力します。i 行目に、i 番目の組の最大公約数と最小公倍数を、この順に空白 1 つで区切って書きます。

制約

T は、1 以上 10000 以下の整数です
a_i と b_i は、どちらも 1 以上 1000000 以下の整数です

入力と出力の例

例 1

12 と 18 は、どちらも 6 で割り切れ、6 より大きい共通の約数はありません。12 でも 18 でも割り切れる最小の数は 36 です。7 と 5 は 1 のほかに共通の約数が無く、最小公倍数は 35 です。

入力

出力

6 36
1 35
4 4

例 2

片方がもう片方を割り切るときは、小さいほうが最大公約数、大きいほうが最小公倍数です。

入力

2
3 1000000
1 1

出力

1 3000000
1 1

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

ユークリッドの互除法で最大公約数 g を求め、最小公倍数は a ÷ g × b で出します。a と b が 100 万以下なので、最小公倍数は 10^12 以下で、JavaScript の数でも正確に表せます。Python には math.gcd もありますが、ここでは互除法を自分で書いています。

Python

import sys

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

data = sys.stdin.read().split()
t = int(data[0])
lines = []
for i in range(t):
    a = int(data[1 + 2 * i])
    b = int(data[2 + 2 * i])
    g = gcd(a, b)
    lines.append(f"{g} {a // g * b}")

print("\n".join(lines))

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const t = data[0];

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

const lines = [];
for (let i = 0; i < t; i++) {
  const a = data[1 + 2 * i];
  const b = data[2 + 2 * i];
  const g = gcd(a, b);
  lines.push(`${g} ${(a / g) * b}`);
}

console.log(lines.join("\n"));

計算量

互除法は、1 組で O(log min(a, b)) 回の割り算で終わります。全部で O(T log M) で、M は数の上限の 100 万です。

遅い解き方は、1 から小さいほうの数まで順に「両方を割り切るか」を試す書き方です。1 組で O(min(a, b))、全部で O(T × M) かかり、どちらの数も 90 万を越える組が 1 万組あるテストでは約 100 億回の割り算になって、どの言語でも時間切れになります。

よくある間違い

最小公倍数を、大きいほうの数の倍数を 1 倍、2 倍と順に試して探す。互いに素な組では小さいほうの数の回数だけかかり、最大公約数を 1 から試すのと同じくらい遅くなります
JavaScript で a / g * b のつもりで a * b / g と書き、a と b がもっと大きい問題で途中の数が正確に表せる範囲を越える。この問題の範囲では越えませんが、割ってから掛ける癖を付けておくと安全です
Python で / を使って割り、最小公倍数が 36.0 のように小数で出力される。整数の割り算は // を使います
互除法の引数の順を気にして a と b を入れ替える処理を書き足す。a が b より小さいときは、1 回目の余りの計算で自然に入れ替わるので要りません

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
t = int(data[0])
pairs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(t)]

# ここから書く

入力

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します