どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

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)