두 정수 N과 P가 있다고 가정해 봅시다. 여기서 P는 N개의 미지의 정수들의 곱입니다. 이때 이 정수들이 가질 수 있는 최대 공약수(GCD)를 구하는 것이 바로 이번 글에서 다룰 문제입니다.
예를 들어 N = 3, P = 24라면, 세 정수의 곱이 24가 되는 조합과 각각의 GCD는 다음과 같습니다.
- {1, 1, 24} → GCD = 1
- {1, 2, 12} → GCD = 1
- {1, 3, 8} → GCD = 1
- {1, 4, 6} → GCD = 1
- {2, 2, 6} → GCD = 2
- {2, 3, 4} → GCD = 1
각 조합의 GCD가 1, 1, 1, 1, 2, 1이므로, 정답은 2입니다.
접근 방법: 소인수분해 활용
이 문제는 P를 소인수분해하면 효율적으로 해결할 수 있습니다. 먼저 P의 모든 소인수를 구하여 해시맵에 저장합니다. N개의 정수가 최대 GCD를 가지려면 소인수들이 모든 정수에 공통으로 분배되어야 하기 때문입니다.
P를 다음과 같이 소인수분해했다고 합시다.
P = p1k1 × p2k2 × … × pnkn
여기서 pi는 소인수입니다. 그렇다면 최대 GCD는 다음과 같이 계산됩니다.
res = p1k1/N × p2k2/N × … × pnkn/N
즉, 각 소인수의 지수를 N으로 나눈 몫을 새로운 지수로 사용하는 것입니다. 예를 들어 P = 24 = 2³ × 3¹이고 N = 3이라면, 최대 GCD는 23/3 × 31/3 = 2 × 1 = 2가 됩니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
long getMaxGCD(long N, long p) {
int gcd = 1;
unordered_map<int, int> prime_factors;
// 2부터 sqrt(p)까지 나누어 보며 소인수와 지수를 기록
for (int i = 2; i * i <= p; i++) {
while (p % i == 0) {
prime_factors[i]++;
p /= i;
}
}
// 루프 종료 후 남은 값이 1이 아니면 그 자체가 소인수
if (p != 1)
prime_factors[p]++;
// 각 소인수의 지수를 N으로 나눈 몫을 지수로 하여 곱함
for (auto v : prime_factors)
gcd = gcd * pow(v.first, v.second / N);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
}
실행 결과
MAX GCD: 2
동작 원리 정리
코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
- 2부터 √P까지 반복하면서 P를 나눌 수 있는 수를 찾아, 해당 소인수와 그 지수를 해시맵에 기록합니다.
- 루프가 끝난 뒤 P가 1이 아니라면, 남은 값 자체가 소인수이므로 해시맵에 추가합니다.
- 각 소인수의 지수를 N으로 정수 나눗셈한 몫을 지수로 삼아 거듭제곱한 뒤, 모두 곱하여 최종 GCD를 구합니다.
시간 복잡도는 소인수분해 과정이 지배적이므로 전체적으로 O(√P)입니다. 덕분에 P가 상당히 큰 경우에도 빠르게 답을 구할 수 있습니다.