백준 1934. 최소공배수

블로그를 티스토리로 이전 중인데, 하루 글 제한 15개가 있어서 우선 남기고 옮기기로 했다.

 

이번 문제는 유클리드 호제법을 이용해서 최소공배수를 구하는 것.

유클리드 호제법이란, a와 b가 있을 때 그 나머지를 이용한 반복으로 최대공약수를 구할 수 있는 방법이다.

a = kb + r 식으로 정수 k와 나머지 r로 나타낼 수 있다고 해보자. 그러면 이 두 수의 최대공약수는 b와 r의 최대공약수와도 같다.

n = int(input())

for i in range(n):
	lst = list(map(int, input().split()))
	a, b = max(lst), min(lst)
	r = a%b
	if r == 0:
		a = b
	while r != 0:
		r = a%b
		a = b
		b = r
	print((lst[0]//a) * (lst[1]//a) * a)