AOJ 0005 GCD and LCM

問題概要

正の整数a, bが与えられるので、これらの最大公約数と最小公倍数を出力せよ。

制約

• 0 ≤ a, b ≤ 2 × 10⁹
• aとbの最小公倍数は、2 × 10⁹を超えない。
• データセットの数は50を超えない。

解法

まず、最大公約数を求める。
ただし、N = min(a, b)とし、
2からNまですべての整数について割り切れるかどうかを判定すると、O(N)かかり、間に合わない。
(AOJは爆速なので間に合うかもしれないが、オーダー的には間に合わないので以下の方法を推奨する)

最大公約数を求めるために、ユークリッドの互除法というアルゴリズムを用いる。
ユークリッドの互除法の原理は、以下が成り立つことである。
a > bのときaとbの最大公約数をGCD(a, b)とし、aをbで割ったときの余りをc(≥ 0)とすると、
GCD(a, b) = GCD(b, c)
となる(証明などは省略、「ユークリッドの互除法」でググると出てくる)。

この方法により、O(log N)で最大公約数を求めることができる。

次に、最小公倍数を求める。
上で求めた最大公約数をGCD(a, b)とすると、以下が成り立つ。
最小公倍数 =

先にa × bをすると、オーバーフローする可能性があるので注意が必要である。

余談

C++では、最大公約数を求める標準ライブラリが存在する。

#include <algorithm>

int main()
{
    __gcd(a, b);
    return 0;
}

コード

#include <iostream>
 
using namespace std;
 
int gcd(int a, int b)
{
    if (a % b == 0) return b;
    return gcd(b, a % b);
} 

int main()
{
    int a, b;
    while (cin >> a >> b) {
        cout << gcd(a, b) << " " << a / gcd(a, b) * b << endl;
    }
    return 0;
}