Алгоритмы: Нахождение степени делителя факториала | C++

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

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

Рассмотрим сначала случай, когда k простое.
Выпишем выражение для факториала в явном виде:
n! = 1.. 2.. 3.. (n-1) n
Заметим, что каждый k-ый член этого произведения делится на k, т.е. даёт +1 к ответу; количество таких членов равно [ n/k^2 ]
Далее, заметим, что каждый k^2-ый член этого ряда делится на k^2, т.е. даёт ещё +1 к ответу (учитывая, что k в первой степени уже было учтено до этого); количество таких членов равно [ n/k^2 ]
И так далее, каждый k^i-ый член ряда даёт +1 к ответу, а количество таких членов равно [ n/k^i ]
Таким образом, ответ равен величине:
n/k + n/k^2 + ... + n/k^i
Эта сумма, разумеется, не бесконечная, т.к. только первые примерно 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, решить задачу для каждого его простого делителя, а потом выбрать минимум из ответов.


Views: 310

Vlod #1 - 8 months ago 0
Голосов: +0 / -0
Будет реализация для случая составного k?
Msey #2 - 8 months ago 0
Голосов: +0 / -0
Vlod, определенно будет. Надо рассмотреть методы типа Полларда, Монте-Карло для разложения на множители, а потом собрать все вместе. Постараюсь найти время на это, а времени очень мало, поэтому пока добавляю самые простые алгоритмы и случаи решения их
Это сообщение удалено