Нахождение степени делителя факториала

Даны два числа: $n$ и $k$ . Требуется посчитать, с какой степенью делитель $k$ входит в число $n!$ , т.е. найти наибольшее $x$ такое, что $n!$ делится на $k^x$ .

Решение для случая простого $k$

Рассмотрим сначала случай, когда $k$ простое.

Выпишем выражение для факториала в явном виде:

$n! = 1\ 2\ 3\ \ldots\ (n-1)\ n$

Заметим, что каждый $k$ -ый член этого произведения делится на $k$ , т.е. даёт +1 к ответу; количество таких членов равно $\lfloor n/k \rfloor$ .

Далее, заметим, что каждый $k^2$ -ый член этого ряда делится на $k^2$ , т.е. даёт ещё +1 к ответу (учитывая, что $k$ в первой степени уже было учтено до этого); количество таких членов равно $\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$ членов отличны от нуля. Следовательно, асимптотика такого алгоритма равна $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$ — это $i$ -ый делитель числа $k$ , входящий в него в степени $p_i$ . Решим задачу для $k_i$ с помощью вышеописанной формулы за $O (\log n)$ ; пусть мы получили ответ ${\rm Ans}_i$ . Тогда ответом для составного $k$ будет минимум из величин ${\rm Ans}_i / p_i$ .

Учитывая, что факторизация простейшим образом выполняется за $O (\sqrt{k})$ , получаем итоговую асимптотику $O (\sqrt{k})$ .