문제

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

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

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

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

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

www.acmicpc.net/problem/2436

  • 입력

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

  • 출력

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

최종 코드

유클리드 호제법을 또 까먹어서^^.. 다시 찾아봤다.

  • 최대공약수: b, a%b의 최대공약수가
  • 최소공배수: (a*b)/최대공약수

그래서 최대공약수 * 최소공배수 = a * b 뭐 이런 식을 이용해서 푸는 건가?했는데 다른 스터디원분의 설명을 들어보니 약간 달랐다.

  • a = 최대공약수 * x
  • b = 최대공약수 * y

여기서 x, y는 서로소이다. 따라서 최소공배수 = 최대공약수 * x * y가 되고, 결과적으로 x * y = 최소공배수 / 최대공약수가 되는 것이다.

예를 들어 최소공배수가 180, 최대공약수가 6이라면 x * y = 180 / 6 = 30 이라는 식을 얻을 수 있다. 따라서 x, y가 될 수 있는 쌍은 (2, 15), (3, 10), (5, 6) 세 가지인데, 이 중에 가장 차가 작은 (5, 6)이 답이 되는 것이다. 결론적으로 답은 x, y에 최대공약수를 곱한 (30, 36)이다.

import sys
from math import gcd

g, l = map(int, sys.stdin.readline().split())
n = l // g # n: 최소공배수 // 최대공약수
a, b = 1, n
min = l
x = 2
while True:
    y = n // x
    # x > y이면 값이 중복되므로 탐색 종료
    # 이 부분이 없으면 시간 초과됨
    if x > y:
        break
    # x가 n과 나누어떨어지고, (x, y)가 서로소인 경우 (=gcd가 1인 경우)
    if n % x == 0 and gcd(x, y) == 1:
        # 두 수의 차가 더 작으면
        if min > y - x:
            min = y - x
            a = x
            b = y
    x += 1

print(a*g, b*g)

최대공약수를 구하는 gcd 메소드를 사용했다.