2436. 공약수

하나를 놓쳐서 시간이 걸린 문제

먼저 A = a*gcd, B = b*gcd라고 놓고, lcm*gcd = A*B니까 식 전개해서

a*b = lcm//gcd여야 한다는 것까지는 파악을 했고

이 때 합이 최소가 되는 두 수여야 하기에 a와 b가 가장 가까운 숫자여야 한다는 것까지는 알았다.

그래서 a*b의 제곱근 근처에서 탐색을 시작해서 a와 b를 찾아내도록 했는데...

a와 b가 서로소여야 한다는 것을 놓쳐서 바로 정답을 맞추지는 못했다.

a와 b가 서로소가 아니라면 gcd가 해당 값이 아니게 되기 때문에 짚고 넘어가야 하는 조건이다.

 

놓치지 말기!

 

import sys
input = sys.stdin.readline

def calc_gcd(a, b) :
    if b == 0 :
        return a
    return calc_gcd(b, a%b)
    

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

ab = lcm//gcd
a = 0
b = 0
for d in range(int(ab**(1/2)), 0, -1) :
    if ab%d == 0 :
        a = d
        b = ab//a
        if calc_gcd(a, b) == 1 :
            print(a*gcd, b*gcd)
            break