백준 알고리즘 1934번 최소공배수(python)

최소공배수는 최대공약수를 안다면 쉽게 구할 수 있다.

-> 최소공배수 = a * b // a와 b의 최대공약수

최대공약수는 유클리우드 호제법을 통해 쉽게 구할 수 있다.

# 유클리우드 호제법은 이런 종류의 문제를 풀 때 자주 사용하게 되므로 기억해놓으면 좋다.

for _ in range(int(input())):
    a, b = map(int, input().split())
    a, b = max(a, b), min(a, b)
    s = a*b
    
    while(b != 0):
        n = a%b
        a = b
        b = n
    
    print(s//a)