문제 개요
두 정수 N과 P가 주어졌다고 가정해 봅시다. 여기서 P는 N개의 알 수 없는 정수들의 곱입니다. 우리가 구해야 하는 값은 바로 이 정수들의 최대공약수(GCD)입니다. 동일한 곱 P를 만들어내는 정수 조합은 여러 가지가 존재할 수 있으며, 가능한 모든 조합을 고려했을 때 가장 큰 GCD를 찾아야 합니다.
예를 들어 N = 3, P = 24인 경우를 살펴보겠습니다. 가능한 조합으로는 {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2, 2, 6}, {2, 3, 4} 등이 있습니다. 각 조합의 GCD는 차례대로 1, 1, 1, 1, 2, 1이므로, 이 경우 정답은 2가 됩니다.
접근 방법
핵심 아이디어는 다음과 같습니다. g가 a1, a2, …, an의 GCD라고 하면, 각 ai는 반드시 g의 배수입니다. 따라서 곱 P = (a1 × a2 × … × an) 역시 gn의 배수가 되어야 합니다. 결국 정답은 P mod gn = 0을 만족하는 가장 큰 g입니다.
이제 P를 소인수분해하여 P = k1p1 × k2p2 × … × kmpm 형태로 나타낼 수 있다고 합시다. 그렇다면 g도 유사한 형태를 가져야 하며, g를 최대화하려면 각 소인수의 지수를 pi / N(정수 나눗셈)로 선택하면 됩니다. 즉, 각 소인수별로 지수를 N으로 나눈 몫만큼만 g에 반영하는 것입니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
using namespace std;
long getMaxGCD(long n, long p) {
int count = 0;
long gcd = 1;
// P를 2로 나눌 수 있는 횟수(지수)를 센다
while (p % 2 == 0) {
p >>= 1;
count++;
}
// 2가 포함되어 있다면 2^(count/n)을 GCD에 곱한다
if (count > 0)
gcd = gcd * (long)pow(2, count / n);
// 3 이상의 홀수 소인수를 검사한다
for (long i = 3; i <= sqrt(p); i += 2) {
count = 0;
while (p % i == 0) {
count++;
p = p / i;
}
if (count > 0) {
gcd = gcd * (long)pow(i, count / n);
}
}
// 마지막에 남은 수가 소수인 경우 처리
if (p > 2)
gcd = gcd * (long)pow(p, 1 / n);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
}
코드 동작 설명
- 2의 지수 세기: P가 2로 나누어떨어지는 동안 계속 나누면서 지수를 셉니다.
- GCD 계산: 각 소인수의 지수를 N으로 나눈 몫(count / n)만큼 거듭제곱하여 GCD에 누적해서 곱합니다.
- 홀수 소인수 검사: 3부터 √P까지 홀수만 확인하며 같은 과정을 반복합니다.
- 남은 소수 처리: 루프 종료 후 2보다 큰 값이 남으면 그것은 소수입니다. 다만 지수가 1이므로 N ≥ 2일 때는 1/n = 0이 되어 GCD에 실질적인 영향을 주지 않습니다.
이 알고리즘은 소인수분해에 기반하므로 시간 복잡도는 O(√P)입니다.
출력 결과
MAX GCD: 2