[Algorithm] [백준] 1934 (Feat. 최대 공약수와 최소 공배수) (유클리드 호제법)

유클리드 호제법

• 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

  • 최대 공약수 : 2개의 자연수 a, b 에 대해서 a를 b로 나눈 나머지를 r 이라고 하면(단, a>b), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
    이 성질에 따라, b를 r로 나눈 나머지 r1을 구하고, 다시 r를 r1로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0 이 될 때까지 반복한다.

  • 최소 공배수 : a, b의 곱을 a, b의 최대 공약수로 나누면 된다. 즉, 주어진 수 중 하나는 그대로 곱하고 하나는 최대 공약수로 나누어 곱하면 된다.

import sys
input = sys.stdin.readline

## 백준 1934 최소 공배수
# gcd : 최대 공약수, lcm : 최소 공배수

t = int(input())

for _ in range(t):
    A, B = map(int, input().split())

    # 먼저 최대 공약수를 구한다.
    # 최대 공약수는 둘 중에 (작은 수)와 (큰수%작은수)의 최대 공약수와 같다.
    # 작은 수가 0이 될 때까지 반복하면 그 때의 큰 수가 최대 공약수이다.
    a, b = A, B
    while b != 0:
        a = a % b
        a, b = b, a

    gcd = a  # 최대 공약수

    # 최대 공약수를 이용하여 최소 공배수를 구한다.
    lcm = A *  B//a
    print(lcm)