백준 1934 최소공배수

문제

---

솔루션

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

    while B>0:
        A,B = B, A%B

    print(result//A)

---

 

깨달은 점

이 문제는 유클리드 알고리즘을 사용해야 풀 수 있다!

최소공배수는 두 수의 곱을 최대공약수로 나눈 값으로 계산한다.

 

여기서 최대공약수를 유클리드 호제법을 이용해야한다.

while B > 0:
    A, B = B, A % B

 

최대공약수를 계산하는 식이다.

 

최대공약수를 이용해서 최소공배수를 구하면 된다.