[BOJ 11688] 최소공배수 찾기

문제 링크 : https://www.acmicpc.net/problem/11688

문제

세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.

입력

첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 10⁶, 1 ≤ L ≤ 10¹²)

출력

첫째 줄에 c를 출력한다. 만약, 가능한 c가 없으면 -1을 출력한다.

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

세 정수 $a, b, L$이 주어졌을 때, $LCM(a, b, c) = L$을 만족하는 가장 작은 자연수 $c$를 찾는 문제다. 최소공배수의 결합 법칙 성질을 이용하면 주어진 식을 다음과 같이 변형할 수 있다.

\[LCM(a, b, c) = LCM(LCM(a, b), c) = L\]

우선 $a$와 $b$의 최소공배수인 $G = LCM(a, b)$를 구한다. 만약 $L$이 $G$의 배수가 아니라면(즉, $L \pmod G \neq 0$), 어떤 자연수 $c$를 선택하더라도 $LCM(G, c) = L$을 만족할 수 없으므로 이 경우에는 $-1$을 출력해야 한다.

$L$이 $G$의 배수라면, $L$과 $G$를 소인수분해했을 때 각 소인수 $p$의 지수를 비교하여 최소의 $c$를 결정할 수 있다. $n$의 소인수 $p$에 대한 지수를 $v_p(n)$이라고 정의할 때, $v_p(L) = \max(v_p(G), v_p(c))$가 성립해야 한다. 가장 작은 $c$를 만들기 위한 조건은 다음과 같다.

1. $v_p(L) > v_p(G)$인 경우: $p$의 지수를 결정하는 주체가 $c$가 되어야 하므로, 반드시 $v_p(c) = v_p(L)$이어야 한다.
2. $v_p(L) = v_p(G)$인 경우: $G$만으로도 $L$의 소인수 지수를 만족하므로, $c$는 해당 소인수를 가질 필요가 없다. 즉, $v_p(c) = 0$일 때 $c$가 최소가 된다.

소스 코드에서는 먼저 need = L / G를 계산하여 $v_p(L) > v_p(G)$인 소인수들에 대해 그 차이만큼인 $p^{v_p(L) - v_p(G)}$를 ret에 담는다. 이후 need의 소인수들을 하나씩 확인하면서, 해당 소인수가 $a$나 $b$에도 포함되어 있다면(즉, $v_p(G) > 0$인 경우) 그만큼을 ret에 다시 곱해주어 결과적으로 $v_p(c) = v_p(L)$이 되도록 보정하는 방식을 사용한다.

$L$의 범위가 최대 $10^{12}$이므로 모든 계산 과정에서 long long 자료형을 사용하며, $1\,000\,000\,000\,000$과 같은 큰 수 연산 시 오버플로우에 주의해야 한다.

소스코드

Github Link : Source Code

참고 알고리즘 : 유클리드 호제법