[백준, BOJ] 2436 - 공약수

1. Question

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

1.1 Input

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

1.2 Output

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

1.3 Example

입력	출력
6 180	30 36

2. Approach

포인트는 gcd*lcm = A*B라는 것.

또한 A+B의 최솟값은 산술기하평균에 의해, A와B가 비슷할 때 나올 것이므로, gcd*lcm의 제곱근부터 검사하면된다.

검사하는 A, B후보중에서 gcd, lcm조건을 만족하는 첫번째 후보를 출력하면 끝.

시간이 676ms가 나왔는데, 더 성능이 좋은 다른 코들 보니까, gcd*lcm의 제곱근이 아니라, lcm / gcd의 제곱근을 검사하고, A = a*gcd, B = b*gcd를 만족하는 a, b후보를 출력하더라.

3. Submission

4. Code

import math

def GCD(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

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

mulAB = gcd * lcm

for A in range(math.ceil(math.sqrt(mulAB)), 0, -1):
    B = mulAB // A
    tempGCD = GCD(A, B)
    if  tempGCD == gcd and A // tempGCD * B == lcm:
        print(A, mulAB // A)
        break