[BOJ] 백준 2436 공약수 Python

import sys
import math

input =  sys.stdin.readline
A,B = map(int,input().split())

x = math.gcd(A,B) 
y = math.lcm(A,B)
z = y // x

result = []
divisor = []
for i in range (1,int(math.sqrt(z))+1):
    if z % i == 0:
        if math.gcd(i,z // i) == 1:
            b = [x*i,x*(z // i)]
            divisor.append(b)
            y = i + (z // i)
            result.append(y)
        else:
            continue
    else:
        continue

z = min(result)
c = result.index(z)
d = " ".join(str(s) for s in divisor[c])
print(d)

실행시간은 40ms

아이디어로는 "최소공배수를 최대공약수로 나눈 후, 몫을 서로소인 두 수의 곱으로 나타내는 것" 이겠다.

또 다른 예를 들어본다면 40과 90을 들어보자.

이 둘의 최대공약수는 10이며, 최소공배수는 360이다.
최소공배수 / 최대공약수 = 36 이며, 이를 서로소인 두 수의 곱으로 나타내는 방법은 (1,36), (4,9) 이렇게 두 쌍만 존재하는데

합을 최소로 하기 위해서는 4와9를 취하고, 최대공약수를 곱해주면 되겠다.

 

즉, 그대로인 40과 90가 되겠다.