[Python] 11688번 최소공배수 찾기

https://www.acmicpc.net/problem/11688

11688번: 최소공배수 찾기

---

 

24/01/25

 

 

단순한 정수론 문제로, 소인수 분해 코드를 효율적으로 작성한다면 쉽게 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

$a, b, L$의 값이 주어질 때, $\mathrm{lcm}(a, b, c) = L$을 만족시키는 가장 작은 $c$의 값을 구하는 것이 문제의 의도이다.

 

$\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)$가 성립하므로, 먼저 $a$와 $b$의 $\mathrm{lcm}$을 구해주었다.

 

이는 유클리드 호제법을 이용하여 두 수의 $\mathrm{gcd}$를 구하면 해결할 수 있고, 유클리드 호제법의 시간 복잡도는 $\mathcal{O}(\mathrm{log}N)$이므로 충분히 빠르게 두 수의 최소 공배수를 구할 수 있다.

 

그 값을 $K$라고 해보자.

 

즉, $\mathrm{lcm}(K, c) = L$을 만족하는 가장 작은 $c$의 값을 구하는 것이 우리의 목표이다.

 

$\mathrm{lcm}$을 구하는 과정을 생각해 본다면, $K$와 $L$을 각각 소인수분해해야 함을 알 수 있다.

 

$K$의 소인수분해 결과와 $c$의 소인수분해 결과에서, 각 소인수 별 지수의 최댓값을 취한 결과가 $L$이다.

 

따라서, 이를 이용하여 구현할 수 있다.

 

만약 $L$을 소인수분해한 결과가 $K$를 소인수분해한 결과보다 특정 소인수에서 그 지수가 작다면, 이는 모순이 되므로 가능한 $c$의 값이 존재하지 않는다.

 

이런 경우에는 $-1$을 출력해주면 된다.

 

그러지 않은 경우에는, $L$을 소인수분해한 결과는 $K$와 $c$의 소인수분해 결과 중 최댓값을 취한 것이므로, 이에 맞춰서 가장 작은 $c$를 취하도록 해주면 된다.

 

소인수분해 과정을 효율적으로 해야할 필요가 있었는데, $\mathcal{O}(\sqrt{N})$의 시간 복잡도를 지니도록 소인수분해를 하도록 했다.

 

처음엔 그냥 나이브하게 $\mathcal{O}(N)$의 시간 복잡도를 가지도록 소인수분해 코드를 작성해서, 시간초과를 받았다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 11688번 최소공배수 찾기
# 정수론, 수학, 유클리드 호제법
import sys
input = sys.stdin.readline

def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a%b
    if r == 0: return b
    return gcd(b, r)

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

def is_prime(a):
    if a == 1: return False
    for i in range(2, int(a**.5)+1):
        if a % i == 0: return False
    return True

def factorization(a):
    if a == 1:
        return {}
    factors = dict()
    if is_prime(a):
        factors[a] = 1
        return factors
    prime = 2
    while prime*prime <= a:
        if a % prime == 0:
            factors[prime] = 0
            while a % prime == 0:
                a //= prime
                factors[prime] += 1
        else:
            prime += 1
    if is_prime(a):
        factors[a] = 1
    return factors

def solve(a, b, L):
    K = lcm(a, b)
    L_factor = factorization(L)
    K_factor = factorization(K)
    c = 1
    for prime, count in L_factor.items():
        if prime in K_factor:
            if K_factor[prime] < count:
                c *= (prime**count)
            elif K_factor[prime] > count:
                print(-1)
                return
            del K_factor[prime]
        else:
            c *= (prime**count)
    if K_factor:
        print(-1)
        return
    print(c)
    return

solve(*map(int, input().rstrip().split()))