Мудрое число по модулю для вычисления степенной функции для очень очень больших натуральных чисел
Привет, я пишу код для расчета P ^ Q, где
P, Q are positive integers which can have number of digits upto 100000
Я хочу результат как
result = (P^Q)modulo(10^9+7)
Пример:
P = 34534985349875439875439875349875
Q = 93475349759384754395743975349573495
Answer = 735851262
Я попытался использовать трюк:
(P^Q)modulo(10^9+7) = (P*P*...(Q times))modulo(10^9+7)
(P*P*...(Q times))modulo(10^9+7) = ((Pmodulo(10^9+7))*(Pmodulo(10^9+7))...(Q times))modulo(10^9+7)
Так как P и Q очень большие, я должен хранить их в массиве и делать по модулю цифра за цифрой.
Есть ли эффективный способ сделать это или какой-то алгоритм теории чисел, который мне не хватает?
заранее спасибо
Решение
Вот довольно эффективный способ:
1) Вычислить p1 = P по модулю 10 ^ 9 + 7
2) Вычислить q1 = Q по модулю 10 ^ 9 + 6
3) Тогда P ^ Q по модулю 10 ^ 9 + 7 равно p1 ^ q1 по модулю 10 ^ 9 + 7. Это равенство верно из-за маленькой теоремы Ферма. Обратите внимание, что p1 и q1 достаточно малы, чтобы поместиться в 32-разрядное целое число, поэтому вы можете реализовать двоичную экспоненту со стандартным целочисленным типом (для промежуточных вычислений достаточно 64-разрядного целочисленного типа, поскольку начальные значения помещаются в 32-разрядные).
Другие решения