[Python/파이썬] 백준 2436번 공약수

2436번: 공약수

 

문제

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

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

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

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

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

입력

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

출력

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

코드

def euclid(a, b):
    if a > b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a


a, b = map(int, input().split())
tmp = b//a
for i in range(int(tmp**(1/2)), 0, -1):
    if tmp % i == 0:
        j = tmp // i
        if euclid(i, j) == 1:
            print(i*a, j*a)
            break

최대공약수가 a, 최소공배수는 b인 두 수를 찾는 문제이다. 

 

이 두 수를 x, y라고 할 때, 두 수의 최대공약수는 a이므로 다음과 같이 쓸 수 있다.

그리고 두 수 x, y를 곱해서 최대공약수로 나눈 값이 최소공배수이므로 b는 다음과 같이 표현할 수 있다.

최대공약수를 a, 최소공배수를 b로 하는 두 수 x, y를 찾기위해서는 i와 j를 찾아야 한다. 그렇기 때문에 최소공배수 b를 최대공약수 a로 나눈 tmp값의 약수를 구하면 되는 것이다. 우리는 두 수의 합이 최소가 되는 경우를 찾을 것이기 때문에 최대한 두 수의 차를 작게 만들어서 곱해지는 수를 작게 만들 것이다. 그러기 위해 tmp의 제곱근에서부터 내림차순으로 탐색하며 답을 찾는다.