как получить по модулю значения в экспоненциальной форме

Question

Вопрос касается оператора по модулю очень больших чисел.

Например, рассмотрим вопрос, в котором нужно вычислить общее число перестановок.Рассмотрим число из 90 цифр, в котором каждое из 9 чисел (от 1 до 9) повторяется 10 раз, поэтому необходимо вычислить 90!/(10!)^9)

После прочтения многих ответов в StackOverflow я использовал для этого логарифмы.

Теперь рассмотрим значение журнала как 1923.32877864.

Теперь мой вопрос: как я могу отобразить ответ (т.е. 10 ^ log10 (значение)) по модулю "m"?

Иэто лучший метод для вычисления возможного числа перестановок?

Редактировать Получил решение:)

Благодаря duedl0r.

Сделал ли онкак вы указали с помощью модульного мультипликативного обратного. Спасибо:)

Answer 1

Я не уверен, действительно ли это возможно и правильно, но позвольте мне обобщить мои комментарии и расширить ответ от Мики Динеску.

Как уже писал Мики:

a × b ≣ _m a _m × b _m

Вы можете использовать это в своем равенстве:

90!/ 10! ^ 9 ≣ _м х

Рассчитать каждый член:

90! _м / 10! ^ 9 _m ≣ _m x

Затем найдите мультипликативный обратный из 10! ^ 9 _m .Затем умножьте обратное на 90! _m .

---

update Это кажется правильным (по крайней мере, для этого случая :)).Я проверил с помощью wolfram:

(90! / 10! ^ 9) мод (10 ^ 9 + 7) = 998551163

Это приводит к тому же результату:

90!мод (10 ^ 9 + 7) = 749079870 10! ^ 9 мод (10 ^ 9 + 7) = 220052161

сделать обратное:

(220052161 * x) мод (10 ^ 9 + 7) = 1 = 23963055

затем:

(749079870 * 23963055) мод (10 ^ 9 + 7) = 998551163

Нет доказательств, но есть некоторые доказательства того, что это можетработа:)

Answer 2

Я бы сказал, что способ вычисления общего числа перестановок по модулю m, где m - произвольное целое число (обычно выбираемое как большое простое число), заключается в использовании следующего свойства:

 (a * b) % m = ((a % m) * (b % m)) % m

Учитывая, что общее число перестановок N равно N! = 1 * 2 * 3 * .. * N, если вам нужно вычислить N! % m, вы можете по существу применить указанное выше свойство для умножения по модулю m, и у вас будет:

 ((((1 * (2 % m)) % m) * (3 % m)) % m) * .. 

EDIT

Для того, чтобы вычислить 90! / (10! ^ 9) значение вы можете упростить факторы и затем использовать умножение по модулю m для вычисления окончательного результата по модулю m.

Вот что я думаю:

90! = 10! * (11 * 12 * .. * 20) * (21 * 22 * ​​.. * 30) * .. * (81 * 82 * .. * 90)

Затем можно переписать исходное выражение как:

(10! * (11 * 12 * .. * 20) * (21 * 22 * ​​.. * 30) * .. * (81 * 82 * .. * 90)) / (10! * 10! * ... * 10!)

В числителе у вас есть произведение 9 факторов - учитывая каждое выражение в скобках как фактор. То же самое относится и к знаменателю (у вас есть 9 факторов, каждый из которых равен 10!).

Первый фактор в знаменателе тривиален для упрощения. После этого у вас осталось 8 пар, которые нуждаются в упрощении.

Таким образом, вы можете учесть каждый термин продуктов и упростить знаменатель. Например:

11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 <=> 11 * 2 * 2 * 3 * 13 * 2 * 7 * 3 * 5 * 2 * 2 * 2 * 2 * 17 * 2 * 9 * 2 * 2 * 5

Знаменатель всегда будет: 2 * 3 * 2 * 2 * 5 * 2 * 3 * 7 * 2 * 2 * 2 * 2 * 3 * 3 * 2 * 5

После упрощения вторая пара уменьшается до: 2 * 2 * 11 * 13 * 17 * 19

То же самое можно применить к каждой последующей паре, и в итоге вы получите простой продукт, который можно вычислить по модулю m, используя приведенную выше формулу.

Конечно, эффективно реализовать алгоритм для упрощения будет непросто, поэтому в конечном итоге должен быть лучший способ, который ускользает от меня сейчас.