[백준 2436 : JAVA] 공약수 / 유클리드 호제법

문제

---

 

 

 

풀이

---

해당 문제를 풀기 위해선 다음의 수학적 정리를 알고 있어야 한다.

임의의 두 수 $x$, $y$에 대해서 최대공약수($gcd(x, y)$) * 최소공배수($lcm(x, y)$) = $x * y$ 이다. (단, $x$, $y$는 최대공약수의 배수)

 

즉, 우리가 해야할 건 $x * y$의 약수이면서, 최대공약수의 배수인 수를 찾아야 한다.

 

알고리즘은 다음과 같다. (편의상, 최대공약수는 A, 최소공배수는 B 라고 표현)

1. 최대공약수와 최소공배수가 주어지면 두 수를 곱해 $x*y$를 구한다.
2. 최대공약수의 배수 중 $xy$의 약수인 수를 $i$라고 한다면, $i$와 $xy/i$ 쌍을 얻을 수 있다.
3. $i$와 $xy/i$ 쌍의 최대공약수가 A라면 이 둘은 우리가 찾고자하는 쌍이다. 
4. 이전에 찾아놓은 $i$와 $xy/i$ 쌍의 합과 비교해 값이 더 작다면 갱신한다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringBuilder sb = new StringBuilder();
            StringTokenizer st = new StringTokenizer(br.readLine());
            long gcd = Long.parseLong(st.nextToken());
            long lcm = Long.parseLong(st.nextToken());
            long ans1 = gcd, ans2 = lcm;

            long xy = gcd * lcm; // gcd(x, y) * lcm(x, y) == x * y 가 성립한다. (수학공식)

            // xy의 약수이면서, 최대공약수의 배수인 것을 찾는다.
            for (long i = 2 * gcd; i * i <= xy; i += gcd) {
                if (xy % i == 0) {
                    long tmp = xy / i;

                    if (gcd(i, tmp) == gcd) {
                        if (ans1 + ans2 > i + tmp) {
                            ans1 = i;
                            ans2 = tmp;
                        }
                    }
                }
            }

            System.out.println(ans1 + " " + ans2);
        } catch (Exception ex) {
            ex.getMessage();
        }
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 

 

 

참고자료

---

[1] travelbeeee.tistory.com/250