[백준 - python] 1934번: 최소공배수

Interrobang 2022. 11. 24. 18:59

문제 링크

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있

www.acmicpc.net

문제 풀이

t = int(input())

for _ in range(t):
    a, b = map(int, input().split())
    result = a * b

    while b > 0:
        a, b = b, a % b

    print(result // a)

*key point: 두 수의 곱을 유클리드 호제법으로 구한 최대공약수로 나누어 준다.