[백준 2436 : JAVA] 공약수 / 유클리드 호제법
2021.03.04
문제 풀이 해당 문제를 풀기 위해선 다음의 수학적 정리를 알고 있어야 한다. 임의의 두 수 $x$, $y$에 대해서 최대공약수($gcd(x, y)$) * 최소공배수($lcm(x, y)$) = $x * y$ 이다. (단, $x$, $y$는 최대공약수의 배수) 즉, 우리가 해야할 건 $x * y$의 약수이면서, 최대공약수의 배수인 수를 찾아야 한다. 알고리즘은 다음과 같다. (편의상, 최대공약수는 A, 최소공배수는 B 라고 표현) 최대공약수와 최소공배수가 주어지면 두 수를 곱해 $x*y$를 구한다. 최대공약수의 배수 중 $xy$의 약수인 수를 $i$라고 한다면, $i$와 $xy/i$ 쌍을 얻을 수 있다. $i$와 $xy/i$ 쌍의 최대공약수가 A라면 이 둘은 우리가 찾고자하는 쌍이다. 이전에 찾아놓은 $i$..