boj 11688 최소공배수 찾기 python

문제링크: 최소공배수찾기

문제 조건

세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.
첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 10^6, 1 ≤ L ≤ 10^12)

문제 관찰

LCM(LCM(a,b), c) = L 임을 알아야 한다.

a b = LCM(a,b) GCD(a,b) 임으로
LCM(a,b) = a*b // GCD(a,b)

그러므로
LCM(LCM(a,b), c) = L 는
LCM(a*b // GCD(a,b), c) = L 이다.

이제 c 를 구해야하는 데 위의 식을 통해 c의 범위는 1 ~ L 임을 추론 할 수 있다.
완전탐색으로 모든 c의 값을 확인 하면 1 ≤ L ≤ 10^12 임으로 터진다.
즉, 시간 복잡도를 줄이거나 답이 될 수 있는 범위를 줄여야 한다.

좀 더 생각해보면
a*b // GCD(a,b) 와 c 의 최소 공배수가 L 이라는 것은
c 는 L의 약수임을 알 수 있다.

그러므로 L의 약수를 구하고 그 값들로 완전 탐색하면 되는 문제이다.

# 최대 공약수 구하기
def GCD(a, b):
    while a % b != 0:
        tmp = a % b
        a = b
        b = tmp
    return b

# 최소 공배수 구하기
def LCM(a, b):
    return (a // GCD(a, b)) * b

# 약수 구하기
def Divisor(n):
# L이 10^12까지므로 logN 시간 복잡도를 가지는 방식으로 
약수를 구해 줘야한다. 
    for i in range(1, int(n**(0.5)+1)):
        if n % i == 0:
            divisorlst.append(i)
            if i * i != n and i * i <= n:
                divisorlst.append(n//i)


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

# L의 약수 리스트
divisorlst = []
Divisor(L)
divisorlst.sort()

Lab = LCM(a, b)
# 정답
ans = -1
for i in range(len(divisorlst)):
# 조건에 맞는 약수를 찾으면 for문을 빠져나온다.
    if LCM(Lab, divisorlst[i]) == L:
        ans = divisorlst[i]
        break
print(ans)