[python] 백준 2436 공약수

https://www.acmicpc.net/problem/2436

2436번: 공약수

 

문제 해결

최소 공배수를 최대 공약수로 나누었을 때의 수를 서로소인 두 인수로 쪼개서 확인하는 작업을 하면 끝

 

CODE

import sys
input = sys.stdin.readline
import math

def solve(res,a):
    target = sys.maxsize
    x, y = -1, -1
    for i in range(1,int(math.sqrt(res)+1)):
        if res%i:continue
        j = res//i
        if math.gcd(i,j) != 1: continue
        if i*a + j*a < target:
            x = i*a; y = j*a
    print(x, y)
    return

if __name__ == "__main__":
    A, B = map(int, input().split())
    diff = B//A
    solve(diff,A)