백준 2436 공약수 파이썬 문제풀이 (python 정수론 최적화)

문제 보러가기

 

GCD 최대공약수

공약수 문제는 정수론의 GCD(최대공약수) 공식을 알고 있어야한다.

 

GCD는 두 수가 있을 때

큰 수를 작은 수로 나눈 나머지를 구하면

이 나머지와 작은 수의 최대공약수는 

큰 수와 작은 수의 최대공약수와 같다는 규칙이다. 

 

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

코드로 구현하면 이와 같다. 

a에서 b를 나눈 나머지 temp를 구하고

b와 temp가 다시 a,b가 된다.

 

결국 나누어 떨어지는 시점까지 진행했을 때의

작은 수 b가 최대공약수가 된다. 

 

LCM 최소공배수

이번엔 최소공배수의 특징을 알아보자.

최소공배수의 특징을 알기 위해 아래 최대공약수를 구하는 방법을 보자.

 

$$A = 2^3 \cdot 3^5 \cdot 5^1 $$

$$B = 2^5 \cdot 3^2 \cdot 5^2$$

 

$$A*B=2^8 \cdot 3^7 \cdot 5^3$$

$$GCD=2^3 \cdot 3^2 \cdot 5^1$$

$$LCM= 2^5 \cdot 3^5 \cdot 5^2$$

 

위 식의 규칙은 재밌게도 A*B에서 GCD를 빼면 LCM이 나온다는 것이다. 

 

def lcm(a,b):
    return a*b//gcd(a,b)

 

백준 공약수 파이썬 문제풀이

이제 이 규칙을 가지고 문제를 풀어보자.

 

어떤 두 자연수의 최대공약수와 최소공배수가 입력되고, 

두 수를 최대공약수, 최소공배수로 하면서 합이 최소가 되는 자연수 쌍을 찾는 문제이다.

 

입력되는 수의 범위는 1억까지 되므로 단순히 쌍을 찾기 위해서 이중 반복문을 쓰면

1억 * 1억이 되어버릴 것이다.

 

여기서 lcm의 규칙을 이용한다.

바로 A*B를 GCD로 나누면 LCM이 된다는 성질.

 

이걸 뒤집어 LCM에서 GCD로 나누면

최대공약수에 곱해져서 A혹은 B를 구할 수 있는

소인수들의 곱을 구할 수 있다.

 

이 소인수를 GCD에 곱한 값들이

GCD와 LCM을 공유하는 a혹은 b 값이 되는 것이다.

 

따라서 LCM / GCD를 한 값의 약수 중 

서로소인 두 값을 각각 GCD에 곱하면 a,b를 구할 수 있고

 

이렇게 구하는 a,b 쌍 중 합이 가장 작은 값을 구하면 된다.

 

import math


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

def lcm(a,b):
    return a*b//g(a, b)

g, l = map(int, input().split())
n = l // g
a,b = 1,n
sum = float('inf')

for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0: # i가 lcm//gcd 의 약수
        j = n//i
        if gcd(i, j) == 1: # 두 약수가 서로소
            if sum > i+j:
                a=i * g
                b=j * g

print(a,b)