세 수의 최소 공배수를 최대로 만드는 방법

1. 문제

 

25342번: 최대 최소공배수 (acmicpc.net)

25342번: 최대 최소공배수

 

2. 풀이

 

3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까

 

두 수 a,b의 최소공배수는?

 

a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소)

 

a,b의 최소공배수는 L = Gnm이다.

 

이 최소공배수가 가장 클려면 어떻게 해야할까?

 

L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다.

 

따라서, L <= ab이다. 

 

그러므로 최소공배수가 최대가 될려면 a,b가 서로소여야한다.

 

3개의 수에서도 마찬가지로 생각해볼 수 있다.

 

a = Gn, b = Gm, c = Gk라고 표현한다면, (n,m,k는 서로소이고 G는 a,b,c의 최대공약수)

 

L = Gnmk이므로, L <= abc여서 a,b,c가 서로소일때 최소공배수가 최대가 될 수 있다.

 

그래서 1부터 n까지에서 3개의 수를 선택할때, 

 

1) 되도록이면 큰 수를 선택할 것

 

2) 3개의 수가 서로소가 되도록 선택할 것

 

------------------------------------------------------------------------------------------------------------------------------

 

그러면 되도록이면 큰 수를 선택할려면 n,n-1,n-2를 선택한다고 해보자.

 

다음 이들이 서로소인지 검사해야한다.

 

3개중 2개의 수가 짝수이면 2개의 수는 반드시 공약수로 2를 가지므로 3개의 수는 절대로 서로소가 아니다

 

따라서 짝수가 2개 이상이 되는지를 생각해봐야한다.

 

-----------------------------------------------------------------------------------------------------------

 

자연수 n은 홀수이거나 짝수이다.

 

n이 홀수라면, n,n-2는 홀수이고 n-1은 짝수이다.

 

1) "인접한 두 자연수는 서로소이다"

 

만약 n,n+1이 서로소가 아니라고 하자. 

 

그렇다면 n = Ga, n+1 = Gb로 표현할 수 있다. n,n+1이 서로소가 아니므로 G는 1이 아니다.

 

그런데 n = Ga = Gb-1인데, G(b-a) = 1이다.

 

a,b,G가 정수이며 G가 1보다 큰데, G(b-a) = 1일수는 없다.

 

따라서 n,n+1은 서로소이다.

 

2) "인접한 두 홀수는 서로소이다"

 

n이 홀수이고 n, n+2에 대하여 서로소가 아니라고 가정해보자.

 

n = Ga, n+2 = Gb인 G가 1보다 크고 a,b가 서로소가 되는 n이 존재한다.

 

그러면 Gb-2 = Ga이므로, G(b-a) = 2이다.

 

그런데, G는 2보다 크다. 왜냐하면.. n이 3 이상의 홀수라고 생각해본다면... G,a,b가 자연수이므로 Ga, Gb는 모두 3보다 크다.

 

따라서, G가 적어도 3 이상이다. 그러므로 G(b-a)=2를 만족하는 자연수 a,b,G는 존재하지 않는다.

 

그래서 인접한 두 홀수는 서로소이다.

 

-----------------------------------------------------------------------------------------------------------

 

따라서 n이 홀수라면, n,n-2는 홀수이므로 서로소이고 n,n-1은 서로소이고 n-1,n-2는 서로소이므로,

 

n,n-1,n-2는 서로소이다.

 

그래서 n이 홀수라면 n(n-1)(n-2)가 최대인 최소공배수가 된다.

 

---------------------------------------------------------------------------------------------------------------------------------

 

이제는 n이 짝수라고 생각해보자.

 

그러면 n,n-2가 짝수이므로 n,n-1,n-2는 적어도 두 자연수가 2를 공약수로 가지므로 서로소가 아니다. 

 

만약 n을 버린다면 (n-1)(n-2)(n-3)이 정답이 되고, n-2를 버린다면 n(n-1)(n-3)이 정답이 된다.

 

그러면 심플하게 둘 중 큰 것을 고르면 되나?

 

아니지 n-1,n-2,n-3의 최소공배수와 n,n-1,n-3의 최소공배수중 최대인걸 고르면 되겠지

 

from sys import stdin

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

def lcm(a,b):
    
    g = gcd(a,b)
    
    n = a//g
    m = b//g
    
    return g*n*m

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())

    if n % 2 == 1:
        
        print(n*(n-1)*(n-2))
    
    else:
        
        a = lcm(n-1,n-2)
        b = lcm(a,n-3)
        c = lcm(n,n-1)
        d = lcm(c,n-3)
        
        print(max(b,d))

 

조금 더 수학적으로 생각해본다면...

 

n을 버린다면 (n-1)(n-2)(n-3)

 

n-2를 버린다면, n(n-1)(n-3)

 

최대가 될려면 n-2를 버리는게 정답이겠지만... 사실 n(n-1)(n-3)을 자세히 보면..

 

n,n-1은 서로소이고 n-1,n-3은 서로소인데 n과 n-3이 서로소라는 보장이 없다

 

n(n-1)(n-3)가 최소공배수라는 보장이 없다

 

하지만 (n-1)(n-2)(n-3)은 n-1,n-2가 서로소이고 n-2,n-3이 서로소이고 n-1,n-3이 서로소니까 최소공배수가 되는데

 

그렇지만 (n-1)(n-2)(n-3)보다 n(n-1)(n-3)가 더 크다

 

그렇다면 n(n-1)(n-3)이 최소공배수가 될려는 조건을 생각해봐야하는데.. n과 n-3이 서로소이면 된다

 

4 1

 

6 3

 

8 5

 

10 7

 

12 9

 

...

 

이렇게 써보면 n과 n-3이 3의 배수이면 서로소가 아니고 그 외의 경우는 서로소이다

 

----------------------------------------------------------------------------------

 

두 수 n,n-3 서로소가 아니라고 할때, 1보다 큰 최대공약수 G에 대하여

 

n = Gm

n-3 = Gk

 

Gm= Gk+3

 

G(m-k) = 3

 

만약 G가 짝수라면, n = 2pm, n-3 = 2pk인데, 2pk는 홀수여야한다. 하지만 모든 자연수 p,k에 대해 모순이다.

 

G가 홀수라면, m이 2의 배수여야 n이 2의 배수가 된다. 마찬가지로 Gk는 홀수여야하는데 G가 홀수이므로 k는 홀수여야한다.

 

그런데 G(m-k) = 3이므로, G = 3이고 m-k = 1이여야한다. 

 

즉, 두 수가 서로소가 아니라면, G = 3이다. 즉 n,n-3이 3의 배수이다.

 

당연히 역인 "n,n-3이 3의 배수이면 두 수는 서로소가 아니다"는 자명하게 참이다. 

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())

    if n % 2 == 1:
        
        print(n*(n-1)*(n-2))
    
    else:
        
        if n % 3 == 0 and (n-3) % 3 == 0:
            
            print((n-1)*(n-2)*(n-3))
        
        else:
            
            print(n*(n-1)*(n-3))

 

------------------------------------------------------------------------------------------------

 

 

그러면 모두 종합해보면? n,n-1,n-2,n-3중 3개를 골라 최소공배수를 구할때, 가장 큰 경우가 정답일듯?

 

from sys import stdin

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

def lcm(a,b):
    
    g = gcd(a,b)
    
    n = a//g
    m = b//g
    
    return g*n*m

t = int(stdin.readline())

for _ in range(t):
    
    n = int(stdin.readline())
        
    a = lcm(lcm(n-1,n-2),n-3)
    b = lcm(lcm(n,n-1),n-3)
    c = lcm(lcm(n,n-1),n-2)

    print(max(a,b,c))

 

참고로, n-3 % 3 == 0하면 틀리더라고

 

n- (3%3) == 0이 먼저 계산되어서 문제되는듯

 

 

.