📢 1934번 문제

백준 문제 링크

🔎 풀이

사용언어 : python
유클리드 호제법(유클리드 알고리즘) 사용
최소공배수는 두 수의 곱에서 최대공약수를 나누어주면 구할 수 있다.

💡유클리드 호제법

• 최대공약수를 구하는 알고리즘

두 개의 자연수 a와 b에서 (a>b) a를 b로 나눈 나머지가 r이라고 했을 때
gcd(a,b) = gcd(b,r) 과 같고 r이 0이면 그때의 b가 최대공약수이다.

🔎 코드

n = int(input())  # 테스트 케이스 갯수

for _ in range(n):
    a, b = map(int, input().split())
    x, y = a, b
    while b != 0:  # 최대공약수 구하기
        a = a % b
        a, b = b, a
    print((x*y)//a) # 최소공배수 구하기