[백준] 11688번 최소공배수 찾기

💡문제접근

• 3개 이상의 수의 최소공배수를 구할 때에는 두 개씩 수를 묶어서 최소공배수를 구하면 된다.
• LCM(a, b, c) >> LCM(LCM(a, b), c)이 성립한다.
• 유클리드 호제법을 이용해서 직접적으로 최대공약수를 구할 수 있고 이 때 두 수의 곱을 최대공약수로 나눈 몫이 최소공배수가 된다.
• LCM(a, b, c) = L을 만족한다는 말은 a, b, c 모두 L의 약수라는 말이 된다.

💡코드(메모리 : 31388KB, 시간 : 156ms)

import sys
input = sys.stdin.readline

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

a, b, L = map(int, input().strip().split())
LCM = a * b // gcd(a, b)

L_li = []
for i in range(1, int(L**0.5)+1):
    if L % i == 0:
        L_li.append(i)
        L_li.append(L // i)

L_li.sort()
flag = False
for i in L_li:
    if LCM * i // gcd(LCM, i) == L:
        print(i)
        flag = True
        break

if flag == False:
    print(-1)

💡소요시간 : 11m