문제 개요
두 개의 정수 n과 k가 주어졌을 때, n! mod (k^x) = 0을 만족하는 x의 최댓값을 구하는 것이 목표입니다.
예를 들어 n = 5, k = 2라고 가정해 보겠습니다. 이때 n! = 120이며, x 값에 따라 나머지는 다음과 같이 변합니다.
- 120 mod 2⁰ = 0
- 120 mod 2¹ = 0
- 120 mod 2² = 0
- 120 mod 2³ = 0
- 120 mod 2⁴ = 8
- 120 mod 2⁵ = 24
- 120 mod 2⁶ = 56
- 120 mod 2⁷ = 120
x = 3까지는 나머지가 0이지만 x = 4부터는 그렇지 않으므로, 정답은 3입니다.
접근 방법
이 문제는 소인수분해와 르장드르(Legendre) 공식을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- k를 소인수분해하여 각 소수 p가 몇 번(v번) 곱해지는지 구합니다.
- n! 안에 소수 p가 몇 번 등장하는지 르장드르 공식으로 계산합니다. 즉, n/p + n/p² + n/p³ + … 의 합을 구합니다.
- 각 소수에 대해 (n!에서의 등장 횟수 ÷ 지수 v)를 계산한 뒤, 그중 최솟값이 곧 x의 최댓값이 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- k의 제곱근에 1을 더한 값을 m에 저장합니다.
- i를 2부터 m까지 반복하며 다음을 수행합니다.
- i = m이 되면 i를 k로 설정하여 남은 인수를 처리합니다.
- k가 i로 나누어 떨어지는 동안 k를 i로 나누고, 나눈 횟수를 v에 기록합니다(소인수의 지수).
- n부터 시작해 t를 i로 계속 나누면서 몫을 u에 누적합니다(르장드르 공식 적용).
- 각 소인수에 대해 u / v를 계산하고, 그중 최솟값을 결과로 저장합니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
using namespace std;
int calculateMaxX(int n, int k) {
int result = n, v, u;
int m = sqrt(k) + 1;
for (int i = 2; i <= m && k > 1; i++) {
if (i == m) {
i = k;
}
for (u = v = 0; k % i == 0; v++) {
k /= i;
}
if (v > 0) {
int t = n;
while (t > 0) {
t /= i;
u += t;
}
result = min(result, u / v);
}
}
return result;
}
int main() {
int n = 5;
int k = 2;
cout<<"Maximum value of x is: " << calculateMaxX(n, k);
}실행 결과
Maximum value of x is: 3
코드 설명
calculateMaxX 함수는 먼저 result를 n으로 초기화합니다. 이후 2부터 √k+1까지의 수로 k를 나누어 소인수를 찾고, 각 소인수 i에 대해 지수 v와 n!에 포함된 i의 총 개수 u를 계산합니다. 내부의 while 루프가 바로 르장드르 공식을 구현하는 부분으로, n을 i로 반복해서 나누며 몫을 모두 더합니다.
마지막으로 u / v 값들 중 최솟값을 반환하는데, 이것이 바로 n! mod (k^x) = 0을 만족하는 x의 최댓값입니다. 시간 복잡도는 소인수분해에 O(√k), 르장드르 공식 계산에 O(log n)이 소요되므로 n과 k가 큰 경우에도 매우 효율적으로 동작합니다.