[백준] 2609 최대 공약수와 최소 공배수 파이썬 풀이 (정수론 및 조합론)

코드

A,B = map(int, input().split())
# 최대 공약수는
# 둘중에 작은 수와 큰수%작은수와의 최대공약수와 같다
# 작은 수가 0이 될때까지 반복한다. 그럼 큰 수가 최대 공약수이다.
a,b = A,B
while b!=0:
    a = a % b
    a, b = b, a

gcd = a
print(gcd)
lcm = A * B//a
print(lcm)

풀이

최대 공약수를 구하는 공식

둘중에 작은 수와 큰수와 작은수를 나눈 나머지와의 최대공약수와 같다

24와 18의 최대 공약수 = 18(작은수)와 6(24%18)의 최대 공약수 = 6(작은수)와 0(18%6)의 최대공약수

작은수가 0이 되면 그때 큰 수가 최대 공약수가 된다

 

최소 공배수는 주어진 수 하나는 그대로 곱하고 하나는 최대공약수로 나눠서 곱해주면 된다

최대 공배수는 이렇게 구하기 때문임!