[알고리즘][Python] 백준(BOJ) 2436 공약수_파이썬

 

2436 공약수    www.acmicpc.net/problem/2436

2436번: 공약수

 

 

문제 풀기 전 공부할 것 : 수학, 정수론, 유클리드 호제법

 

 

 

 

 

 

 

풀이

<내용>

• 최소공배수는 숫자1 x 숫자2 / 최대공약수이다.
• 최소공배수 x 최대공약수는 숫자1 x 숫자2이다.
• 최소공배수 / 최대공약수는 숫자1' x 숫자2'이다.(이때, 숫자1'과 숫자2'는 서로소이다.)
  • 숫자1 = 숫자1' x 최대공약수
  • 숫자2 = 숫자2' x 최대공약수
• 숫자1'+숫자2' 중 가장 작은 것을 찾으면 된다.

 

 

<코드>

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

g, l = map(int, input().split())
div = l // g
a, b = 1, div
for i in range(1, div//2+1):
    if div % i == 0:
        c = i
        d = div//i
        if gcd(c, d) != 1:
            continue
        if a+b > c+d:
            a = c
            b = d
print(a*g, b*g)