어떤 수를 서로소 쌍의 곱으로 빠르게 분해하는 방법

1. 문제

 

2436번: 공약수 (acmicpc.net)

2436번: 공약수

 

2. 풀이

 

최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까

 

$$x = Gk_{1}$$

 

$$y = Gk_{2}$$

 

이 때 L은 다음과 같이 구할 수 있다

 

$$L = Gk_{1}k_{2}$$

 

따라서 $k_{1}k_{2}$는 L//G로 일정하다.

 

그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다.

 

여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연수이다.

 

서로소가 되는 두 자연수는 어떻게 찾을 수 있을까?

 

유클리드 호제법을 이용해서 두 수의 최대공약수가 1인지 확인해보면 빠르다.

 

from sys import stdin

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

G,L = map(int,stdin.readline().split())

x = L//G

min_value = 200000001

for i in range(1,int(x**(1/2))+1):

    k1 = i

    if x % i != 0:

        continue

    k2 = x//i

    if gcd(k1,k2) == 1:

        if min_value > G*k1 + G*k2:

            min_value = G*k1 + G*k2

            answer = [G*k1, G*k2]

answer.sort()

print(*answer)

 

 

3. 최적화된 풀이

 

최솟값을 구하기 위해 min_value = 200000001을 놓고 비교하는 과정을 두었는데

 

사실 이렇게 하지 않아도 된다

 

문제는 바꿔 생각하면, xy = L//G로 일정할때, x+y가 최소가 되는 자연수 x,y를 구하는 문제다.

 

x,y가 자연수이므로 y = (L//G)/x가 된다.

 

그러므로 x + y = x + (L//G)/x이다.

 

f(x) = x + k/x가 최소가 되는 x는 어디서 생길까?

 

f(x)를 미분하면 $$f'(x) = 1 - \frac{k}{x^{2}}$$

 

x의 범위는 위에서 보인 것처럼 1부터 $\sqrt{L//G}$까지 이다. 여기서 k = L//G

 

그러니까, $x^{2}$의 범위는 1 <= x <= (L//G=k)

 

그러므로 f'(x)는 구간의 모든 x에서 0이하이다.

 

 

 

따라서 f(x)는 구간에서 항상 감소하는 함수이다.

 

그러므로 x가 가장 클때, f(x) = x+y는 최소가 된다

 

그러므로 i를 1부터 L//G의 제곱근까지 반복해서

 

L//G가 i로 나누어 떨어지고, i와 (L//G)/i의 최대공약수가 1인 조건을 만족하는 i를 임시변수에 저장해놓는다

 

반복문이 끝나면 그 i는 최대 i가 된다.

 

따라서 그 때의 i가 x+y가 최소가 되는 x,y를 구하게 해준다

 

from sys import stdin

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

G,L = map(int,stdin.readline().split())

x = L//G

for i in range(1,int(x**(1/2))+1):

    if x % i == 0 and gcd(i,x//i) == 1:

        answer = i

print(G*answer, G*(x//answer))