1

Тема: "Вычисление факториала по модулю"

Видимо, я что-то недопонял, но зачем вообще тут нужно быстрое возведение в степень? Нам же надо только -1 возводить в степень, а это зависит просто от четности показателя.

И еще вопрос, можно как-нибудь за разумное время посчитать факториал n! по простому модулю p, если n порядка 10^18, а p порядка 10^9 ?

2

Re: "Вычисление факториала по модулю"

Если предпосчитать все n! такие, что n<p и n%1000000==0 (можно взять другой модуль, но тут выходит компромисс между быстродействием и размером программы), то чтобы посчитать (n%p)! нам уже не нужно пересчитывать его с единицы, а достаточно начать идти от ближайшего предподсчитанного факториала. Правда это работает только если p заранее известно.

3

Re: "Вычисление факториала по модулю"

Исправил статью. Кстати, в Вики эта статья уже содержала исправленный вариант.