[백준] 2436번 공약수

💡문제접근

• 두 수 A, B를 나눈 몫의 곱의 결과와 최대공약수를 곱해주면 최소공배수가 나온다.
• 최대공약수와 최소공배수의 곱의 제곱근을 기준으로 for문을 돌려 두 자연수의 합이 최소가 되는 순간의 두 수를 출력하고 멈춘다.

💡코드(메모리 : 31256KB, 시간 : 468ms)

import sys
input = sys.stdin.readline

GCD, LCM = map(int, input().strip().split())
# GCD : 최대공약수
# LCM : 최소공배수

num = GCD * LCM # 최대공약수와 최소공배수의 곱

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

for A in range(int(num**0.5)+1, 0, -1):
    B = num // A
    temp = gcd(A, B)
    if temp == GCD and temp * (A // temp) * (B // temp) == LCM:
        print(A, B)
        break

💡소요시간 : 34m