Знаете ли вы какой-либо алгоритм, который эффективно рассчитывает факториал после модуля?
Например, я хочу запрограммировать:
for(i=0; i<5; i++)
sum += factorial(p-i) % p;
Но p
это большое число (простое число) для непосредственного применения факториала .
В Python эта задача действительно проста, но я действительно хочу знать, как оптимизировать.
algorithms
efficiency
integers
jonaprieto
источник
источник
(X!) (mod (X+1))
, или более общий(X!) (mod Y)
? И я предполагаю, что наfactorial(100!)
самом деле это не значит, что вы хотите применить функцию факториала дважды.Ответы:
(Этот ответ был первоначально опубликован в вопросе аскером jonaprieto .)
Я помню теорему Вильсона и заметил мелочи:
В приведенной выше программе лучше написать:
И вы можете найти потому что , поэтому с помощью расширенного евклидова алгоритма вы можете найти значение , то есть обратный модуль. НОД ( р , р - я ) = 1 ( р - я ) - 1( п - я )- 1 НОД( p , p - i ) = 1 ( п - я )- 1
Вы также можете просмотреть те же конгруэнции, например: поэтому сумма равна: и если вы сначала факторизуете факториалы, вы получите И, вуаля, обратный модуль более эффективен, чем факториалы. (-24)-1+(6)-1+(-2)-18⋅(-24)-1
источник
Пример, который вы публикуете, очень тесно связан с проблемой Эйлера # 381. Поэтому я опубликую ответ, который не решит проблему Эйлера. Я опубликую, как вы можете вычислить факториалы по модулю простого числа.
Итак: Как рассчитать! по модулю р?
Быстрое наблюдение: если n ≥ p, то n! имеет фактор р, поэтому результат равен 0. Очень быстро. И если мы игнорируем требование, что p должно быть простым, то пусть q будет наименьшим простым фактором p, и n! по модулю p равно 0, если n ≥ q. Также нет особых причин требовать, чтобы p было простым, чтобы ответить на ваш вопрос.
Теперь в вашем примере (п - я)! для 1 ≤ я ≤ 5 подошел. Вам не нужно вычислять пять факториалов: Вы вычисляете (n - 5) !, умножаете на (n - 4), идете, получаете (n - 4) !, умножаете на (n - 3), чтобы получить (n - 3)! и т.д. Это сокращает работу почти в 5 раз. Не решайте проблему буквально.
Вопрос в том, как рассчитать n! по модулю м. Очевидным способом является вычисление n !, числа с примерно n log n десятичными цифрами, и вычисление остатка по модулю p. Это тяжелая работа. Вопрос: Как мы можем получить этот результат быстрее? Не делая очевидных вещей.
Мы знаем, что ((a * b * c) по модулю p = (((a * b) по модулю p) * c) по модулю p.
Чтобы вычислить n !, мы обычно начинаем с x = 1, затем умножаем x на 1, 2, 3, ... n. Используя формулу по модулю, мы вычисляем n! по модулю p без вычисления n !, начиная с x = 1, а затем для i = 1, 2, 3, .., n мы заменяем x на (x * i) по модулю p.
У нас всегда есть x <p и i <n, поэтому нам нужна только достаточная точность для вычисления x * p, а не гораздо более высокая точность для вычисления n !. Так что посчитать! По модулю p для p ≥ 2 предпринимаем следующие шаги:
(В некоторых ответах упоминается теорема Уилсона, которая отвечает на вопрос только в очень особом случае из приведенного примера и очень полезна для решения проблемы Эйлера # 381, но в целом бесполезна для решения поставленного вопроса).
источник
Это моя реализация использования теоремы Вильсона:
Функция factMOD вызывается для вычисления (n!)% MOD, когда MOD-n мало против n.
Кто-нибудь знает другой эффективный подход, когда это не так (например, n = 1e6 и MOD = 1e9 + 7)?
источник