25_백준 1934번 파이썬 최소공배수

최대 공약수를 유클리드 호제법으로 구한 뒤
최소 공배수를 구하는 식인 두 수를 곱한 값을 최대 공약수로 나눠서 구한다.

 

* 유클리드 호제법

x > y 일 때, x 를 y로 나눈 나머지를 R이라고 할 때 x와 y 의 최대공약수는 y와 R의 최대공약수와 같습니다.

 

 

* 최소공배수

최소공배수는 x와 y의 곱을 최대공약수로 나눈 몫이다.

-> x = a*R , y = b*R 이므로 x * y // R = a*b*R*R // R = a*b*R

 

* 풀이

from sys import stdin
# 최대 공약수
# 유클리드 호제법
def gcd(x, y):
    # y가 0이 될 때까지 반복
    while y:
        # y를 x에 대입
        # x를 y로 나눈 나머지를 y에 대입
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y // gcd(x, y)

n = int(stdin.readline())

for _ in range(n):
    a, b = map(int, stdin.readline().split())
    print(lcm(a,b))