파이썬(python) 1934번 최소공배수

문제링크

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

import sys

t = int(sys.stdin.readline())

for i in range(t):
    a,b = map(int, sys.stdin.readline().split())
    A,B = a,b
    while a!=0:
        b = b%a
        a,b = b,a
    gcd = b
    lcm = A*B//b
    print(lcm)

먼저 최대공약수를 구한다.

최대 공약수는 둘 중에 작은 수와 큰 수%작은 수와의 최대공약수와 같다고 본다.

작은 수가 0이 될 때까지 반복. 거기서 큰 수가 최대공약수다.

두 수 A와 B를 곱한 후, 최대공약수로 나눠주면 최소공배수가 된다.