greentea31's Note

https://www.acmicpc.net/problem/2609

풀이 과정

최대공약수는 유클리드 호제법을 이용해서 구할 수 있다.

GCD(a, b)를 a, b의 최대공약수라고 하고 a % b = r 이라고 하면 GCD(a, b) = GCD(b, r)이 성립한다. 이 과정을 반복해서 GCD(c, 0)이 되면 c가 두 수 a, b의 최대공약수다.

ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) => 24와 16의 최대공약수는 8

최소공배수 LCM은 a*b / GCD임이 알려져 있으니 이를 통해 구하면 된다.

ex) LCM(24, 16) = 24 * 16 / 8 = 48 => 24와 16의 최소공배수는 48

코드

import sys

def gcd(a, b):
    if b == 0: return a
    else: return gcd(b, a%b)

lcm = lambda a, b: a*b//gcd(a, b)


a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))