[백준 python 1934] 최소공배수

[Bronze I] 최소공배수 - 1934

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

유클리드 호제법, 수학, 정수론

제출 일자

2023년 12월 13일 19:28:16

문제 설명

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

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    a2, b2 = a, b
    while a2 % b2 != 0:
        a2, b2 = b2, a2 % b2
    print(a*b// b2)

풀이

이 문제를 풀기 위해서는 최소공배수와 최대공약수의 관계에 대해 알면 좋다.

최대공약수를 G, 최소공배수를 L로 했을때, 둘의 관계는 L = G * A * B 또는 A * B = G * L이다.

그렇다면 최대공약수는 어떻게 구하면 될까?

이는 유클리드 호제법을 활용하면 된다. 유클리드 호제법을 이해하기 쉽도록 설명하자면

두 자연수 A, B(A ≥ B)에 대하여

A ÷ B=p ····· r (p ≠0)에서

A=Bp+r (0≤ r 〈 B)이다.(나눗셈의 정리)

A와 B의 최대공약수는 Bp+r과 B의 최대공약수와 같다.

여기서 Bp는 B의 배수이고, r는 B의 배수가 아니므로(∵0≤ r 〈 B)

A와 B의 최대공약수는 B와 r의 최대공약수와 같다.

∴ G(A, B)=G(B, r)

그래서 위와 같은 풀이로 풀게 되면 b2에 최대공약수가 담기게 되면서 A * B = G * L 식을 활용하여 A와 B에 최대공약수를 나누어주게 되면 최소공배수가 나오게 된다.