팩토리얼 약수의 거듭제곱 구하기¶
두 수 $n$과 $k$가 주어집니다. $k^x$가 $n!$을 나누는 가장 큰 정수 $x$를 구하십시오.
소수 $k$¶
먼저 $k$가 소수인 경우를 살펴봅시다. 팩토리얼을 명시적으로 풀어 쓴 식은 다음과 같습니다.
곱에서 $k$번째 원소마다 $k$로 나누어떨어지므로 답에 $+1$을 더한다는 점에 주목하십시오. 이러한 원소의 개수는 $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$입니다.
다음으로, $k^2$번째 원소마다 $k^2$로 나누어떨어지므로 답에 $+1$을 한 번 더 더합니다($k$의 첫 번째 거듭제곱은 앞 문단에서 이미 세었습니다). 이러한 원소의 개수는 $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$입니다.
이와 같은 방식으로, 모든 $i$에 대해 $k^i$번째 원소마다 답에 $+1$을 한 번 더 더하며, 이러한 원소는 $\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$개입니다.
최종 답은 다음과 같습니다.
이 결과는 르장드르 공식으로도 알려져 있습니다. 대략 처음 $\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 = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$로 나타낼 수 있습니다. 각 $k_i$에 대해 위에서 설명한 알고리즘을 사용하여 $n!$에 $k_i$가 몇 번 포함되는지 구합니다. 이 값을 $a_i$라고 합시다. 합성수 $k$에 대한 답은 다음과 같습니다.