[백준 02436] 공약수 [Python]

문제

https://www.acmicpc.net/problem/2436

 

---

풀이

두 수 A, B의 GCD, LCM이 주어질 때, 두 수의 합이 최소가 되는 수를 구하는 문제다.

이때 두 수의 범위 2 ~ 1억에 대해 GCD, LCM을 전부 구해 비교하는 방법은 시간 초과가 발생한다.

탐색 범위를 좁혀보자.

$G = GCD(A, B), L = LCM(A, B)$일 때, $AB = GL$, $A = Gx$, $B = Gy$

이므로 $AB = G^2xy = GL, xy = \frac{L}{G} = K$가 성립한다.

K의 모든 약수 쌍 중 $GCD(A, B) = G*GCD(x, y)$를 만족해야 하므로, $GCD(x, y) = 1$인 약수만 해당된다.

    K = LCM // GCD
    x, y = 0, 0
    for d in range(1, int(K**0.5) + 1):
        if K % d == 0 and gcd(d, K // d) == 1:
            x = d
            y = K // d

두 수의 합이 최소가 되기 위해서는 가장 마지막에 찾은 $x, y$에 $G$를 곱하면 된다.

    # Output
    print(GCD * x, GCD * y)

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/02436.py