#25: 최소공배수

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

유클리드 방식의 최대공약수 구하는 방식을 이해해야겠다 생각하여 파이썬으로 그 방식을 구현한 코드를 이해하려 하였다. 하지만 우선 그 수학적 논리를 이해하는게 우선이라 생각하여 다음 자료를 찾았다.

x와 y의 최대공약수는 y와 나머지의 최대공약수와 같다.

이것을 구현한 코드가 다음과 같다.

def gcd(x, y):
    while y:
        x, y = y, x % y

    return x

항해99 슬랙에다 질문해본 결과

1. while y란 y = 0일 때 무한 loop에서 빠져나온다는 의미이다.

2. x, y = y, x%y란 x = y와 y = x % y를 한 번에 표현한 것이다.

 

그러고 나면 최소공배수는 두 수의 곱에서 최대공배수를 나눈 값과 같다. 결과 코드는 다음과 같다.

T = int(input())

def gcd(x, y):
    while y:
        x, y = y, x % y

    return x


def lcm(x, y):
    return x * y // gcd(x, y)


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

 

 

통과!