백준 - 2436 공약수 [유클리드 호제법]

 

2436번: 공약수

 

해당 문제는 최대공약수와 최소공배수가 주어지면,

주어진 최대공약수와 최소공배수를 만족시키는 두 수 A, B 중 A + B가 가장 작은 경우를 찾는 문제입니다.

 

접근 전략

• A X B 는 최대공약수 X 최소공배수 와 같습니다.
• 완전탐색으로 가능한 모든 경우의 수를 찾는다.
  • 최대공약수의 배수들을 탐색한다.
  • 최대공약수의 배수들 중 A X B 와 나누어 떨어지는 경우를 찾는다.
  • 주어진 최대공약수와 탐색하는 수의 최대공약수가 같은 경우를 찾는다. (유클리드 호제법으로 최대공약수를 빠르게 찾을 수 있음)
  • 이들 중 합이 가장 작은 수를 찾는다.

 

파이썬

def euclidean(a: int, b: int):
    while b:
        a, b = b, a % b
    return a

def solution(gcd: int, lcm: int):
    ab = gcd * lcm
    A = gcd
    B = lcm
    for a in range(gcd, int(ab ** 0.5) + 1, gcd):
        if ab % a == 0:
            b = ab // a
            if euclidean(a, b) == gcd:
                if A + B > a + b:
                    A, B = a, b
    print(A, B)

gcd, lcm = map(int, input().split())
solution(gcd, lcm)

 

자바

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        solution(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
    }

    static void solution(int gcd, int lcm) {
        long ab = (long) gcd * lcm;
        int A = gcd;
        int B = lcm;
        for (int a = gcd; a <= Math.sqrt(ab); a += gcd) {
            if (ab % a == 0) {
                int b = (int) (ab / a);
                if (getGCD(a, b) == gcd) {
                    if (A + B > a + b) {
                        A = a;
                        B = b;
                    }
                }
            }
        }
        System.out.println(A + " " + B);
    }

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

 

깃허브 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/9c90e531e82d56f82695949d3fdf4c2e51868b3a/%EB%B0%B1%EC%A4%80/Gold/2436.%E2%80%85%EA%B3%B5%EC%95%BD%EC%88%98