두 수의 최소공배수를 구하는 문제입니다. 최소공배수는 최대공약수를 이용하여 구할 수 있는데, 그 관계는 아래와 같습니다. G를 최대공약수, L을 최소공배수라고 하면
를 만족합니다. 따라서 이 문제는 최대공약수를 구하는 문제와 같게 됩니다. 따라서 유클리드 호제법을 이용하여 최대공약수를 구한 뒤, 두 정수의 곱에서 최대공약수를 나눈 값을 출력하면 됩니다.
증명
두 자연수 A와 B가 있고, 최대공약수를 G라고 하자. 그러면
$$
A=aG,B=bG
$$
이 때, 공배수를 l이라고 하면 l은 아래의 조건을 만족시켜야 한다.
$$
A|l, B|l
$$
그리고 이를 만족하는 l 중 가장 작은 수를 최소공배수(L)이라고 한다.
$$
A|l, B|l\\
\Rightarrow l=kA, l=mB
\Rightarrow kaG=l=mbG
$$
이 때, a와 b는 서로소이므로 kaG와 mbG가 같으려면 m은 a를 약수로, k는 b를 약수로 가져야한다. 그런 수 중 가장 작은 자연수는 각각 a와 b이다. 따라서,
$$
L=kaG=baG=abG\\
=\frac{aG\times bG}{G}=\frac{AB}{G}
$$
PS알못 OrbitHv의 PS