자연수를 더해서 최소공배수를 최소로 만들기

1. 문제

 

11414번: LCM (acmicpc.net)

11414번: LCM

 

2. 풀이

 

임의의 정수 k에 대하여 $$gcd(a,b) = gcd(a+kb,b)$$를 이용하자.

 

그러면, $$gcd(a+n, b+n) = gcd(a-b, b+n) = gcd(a+n, b-a)$$를 얻는다.

 

그래서 a < b이면, $a+n \leq gcd(a+n,b+n) \leq b-a$

 

최대공약수로 gcd(a+n,b+n) = gcd(a-b,b+n) = gcd(b-a,b+n) = b-a라고 한다면...

 

(gcd(a,b) = gcd(abs(a),abs(b))이기 때문)

 

b+n이 b-a의 배수라는 말이다.

 

즉, $(b-a)*i \geq b+n > b$이므로, $$i > \frac{b}{b-a}$$

 

어떤 i에서 최소공배수가 최소가 될까?

 

a+n,b+n의 최소공배수는 $lcm(a+n,b+n) = \frac{(a+n)(b+n)}{b-a}$이므로, n이 최소이면 최소공배수가 최소가 된다.

 

즉, i가 최소이면 n이 최소이므로, 그러한 i에서 gcd(a+n,b+n) = b-a일때 최소공배수가 최소가 된다.

 

최소가 되는 정수 i는 어떻게 구하나?

 

i > 3.2123일때 i = 4

 

그래서 math.ceil(b/(b-a))로 구할 수 있다.

 

a,b = map(int,input().split())

if a > b:
    
    a,b = b,a

x = b-a

i = math.ceil(b/x)

n1 = x*i-b
min_lcm = (a+n1)*(b+n1)//x

 

문제는 b/(b-a)가 정수가 되는 경우에는 1을 더해줘야한다.

 

정수가 되는 경우가 i > 3처럼 부등식이 세워지는데 i = 3보다 커야한데 i = math.ceil(b/x) = 3이 나와서 그대로 쓰면 오답

 

a,b = map(int,input().split())

if a > b:
    
    a,b = b,a

x = b-a

i = math.ceil(b/x)

if x*i == b:
    
    i += 1

n1 = x*i-b
min_lcm = (a+n1)*(b+n1)//x

 

이렇게 구한 b+n = x*i이므로, n = x*i - b이고 그럴때 최소공배수는 이 n을 사용해서 (a+n)(b+n)/x로 구할 수 있다.

 

이제 최대공약수로 gcd(a+n,b+n) = gcd(a+n,b-a) = a+n이라고 한다면...

 

b-a의 약수가 a+n이 된다는 말이다.

 

그러니까 b-a의 약수를 $O(\sqrt{n})$으로 모두 구하고, 모든 약수에 대해 a+n과 비교해서 n을 구한다.

 

n이 자연수가 되는 그러한 n에 대하여 최소공배수가 최소로 갱신될때 n을 저장해놓는다

 

import math

def divisor(n):
    
    result = []
    
    for i in range(1,int(n**(1/2))+1):
        
        if n % i == 0:
            
            if n//i == i:

                result.append(i)

            else:

                result.append(i)
                result.append(n//i)

    return result 

a,b = map(int,input().split())

if a > b:
    
    a,b = b,a

x = b-a

if x == 0:
    
    print(1)

else:

    i = math.ceil(b/x)

    if x*i == b:
        
        i += 1

    n1 = x*i-b
    min_lcm = (a+n1)*(b+n1)//x

    d = divisor(x)

    for i in d:
        
        n = i - a

        if n > 0:
            
            if b+n < min_lcm:
                
                n1 = n
                min_lcm = b+n
    print(n1)

 

여기서 문제는 a = b인 경우가 있는데 그런 경우에 최소공배수가 최소가 되는 a+n, b+n은 뭐가될까

 

a = b이면 a+n,b+n의 최소공배수는 당연히 a+n이 되므로, n = 1이어야 최소공배수가 최소이면서 n이 최소가 될 수 있다

 

이런 경우를 예외케이스로 처리