GCD and LCM

最大公約数と最小公倍数

問題ページ

解き方

pythonのmathモジュールにはmath.gcd関数がありますがこれはバージョン3.5で追加されており、現状Aizu Online Judgeのpythonのコンパイラは3.4.2なのでこれは使うことができません。なので、ユークリッドの互除法を使って最大公約数を求めます。

ユークリッドの互除法 - Wikipedia

最大公約数と最小公倍数には以下のような関係があります。

正の整数a, bにおいて、最大公約数gcd(a,b)と最小公倍数lcm(a,b)は

gcd(a,b) x lcm(a,b) = a x b　という関係である。

この関係を利用して最小公倍数を求める。

コード(python)

def GCD(m, n):
    while n:
        m, n = n, m % n
    return m

while True:
    try:
        a, b = map(int, input().split())
    except:
        break
    if a < b:
        a, b = b, a
    gcd = GCD(a, b)
    lcm = (a * b) // gcd
    print(gcd, lcm)