두 수 n과 k가 주어집니다. 약수 k가 수 n!에 몇 제곱으로 들어 있는지, 즉 n!이 k^x로 나누어떨어지는 가장 큰 x를 구해야 합니다.
k가 소수인 경우의 풀이 먼저 k가 소수인 경우를 살펴봅시다.
팩토리얼을 명시적으로 풀어 써 봅시다:
n! = 1\ 2\ 3\ \ldots\ (n-1)\ n
이 곱에서 k번째 항마다 k로 나누어떨어지므로 답에 +1을 더한다는 점에 주목하십시오. 이러한 항의 개수는 \lfloor n/k \rfloor입니다.
다음으로, 이 수열의 매 k^2번째 항은 k^2로 나누어떨어지므로 답에 +1을 더 더한다는 점에 주목하십시오(k의 1제곱은 이미 앞에서 셌다는 점을 고려합니다). 이러한 항의 개수는 \lfloor n/k^2 \rfloor입니다.
이와 같이 계속하면, 수열의 k^i번째 항마다 답에 +1을 더하며, 이러한 항의 개수는 \lfloor n/k^i \rfloor입니다.
따라서 답은 다음 값과 같습니다:
\frac{n}{k} + \frac{n}{k^2} + \ldots + \frac{n}{k[…]
물론 이 합은 무한하지 않습니다. 대략 처음 \log_k n개의 항만 0이 아니기 때문입니다. 따라서 이 알고리즘의 시간 복잡도는 O(\log_k n)입니다.
구현:
int fact_pow (int n, int k) { int res = 0; while (n) { n /= k; res += n; } return res; } 합성수 k인 경우의 해법 같은 아이디어를 여기에 직접 적용할 수는 없습니다.
하지만 k를 소인수분해하여 각 소인수에 대해 문제를 푼 다음, 그 답들 중 최솟값을 고를 수 있습니다.
더 형식적으로 말하면, k_i를 수 k의 i번째 약수라 하고, 이 약수가 k에 p_i제곱으로 포함된다고 합시다. 위에서 설명한 공식을 이용하여 k_i에 대한 문제를 O (\log n)에 풉니다. 이때 얻은 답을 {\rm Ans}_i라고 합시다. 그러면 합성수 k에 대한 답은 {\rm Ans}_i / p_i 값들 중 최솟값이 됩니다.
가장 단순한 방법으로 인수분해를 O (\sqrt{k})에 수행할 수 있다는 점을 고려하면, 최종 점근적 복잡도는 O (\sqrt{k})가 됩니다.