Алгоритм — модульное возведение в норму для большого мода в переполнении стека

Question

Алгоритм — модульное возведение в норму для большого мода в переполнении стека

Это код, который я использую для расчета (n^p)%mod, К сожалению, это не подходит для больших значений mod (в моем случае mod = 10000000000ULL) когда я звоню main() метод. Любая идея; Зачем?

ull powMod(ull n, ull p, ull mod) {
ull ans = 1;
n = n%mod;
while(p) {
if(p%2 == 1) {
ans = (ans*n)%mod;
}
n = (n*n)%mod;
p /= 2;
}
return ans;
}

Вот, ull является typedef для unsigned long long,

4

algorithm c++cryptography exponentiation modular-arithmetic

Решение

Другие решения

Кажется, что вы не можете избежать этого.

Если mod является 10000000000ULL, в (a*b)%c в вашей программе оба a а также b меньше, чем мод, поэтому мы относимся к ним как 9999999999ULL, a*b будет 99999999980000000001, но unsigned long long могу только выразить 2^64-1=18446744073709551615 < 99999999980000000001 поэтому ваш метод будет переполнен.

1

Одна из возможных проблем здесь, кажется, что когда вы делаете (a*b)%c, a*b сама часть может переполниться, что приведет к неправильному ответу. Одним из способов обойти это является использование идентичности, которая

(a*b)%c

эквивалентно

(a%c * b%c)%c

Это также предотвратит переполнения в промежуточных умножениях.

0

Ваша строка кода

 n = (n*n)%mod;

многократно выполнен.
Пока n меньше, чем mod, это может привести к оценке (mod-1) * (mod-1) в определенный момент времени.

На входе n может быть не таким большим, но упомянутая строка кода увеличивает n в цикле.

0

Источник

Accepted Answer

Да, вы можете сделать это в C ++. Как отмечали другие, вы не можете сделать это непосредственно. Используя небольшую каплю теории чисел, можно разложить проблему на две управляемые подзадачи.

Сначала посмотрим, что 10^10 = 2^10 * 5^10, Оба фактора взаимно просты, поэтому вы можете использовать Китайская теорема об остатках найти силу по модулю 10^10 используя полномочия по модулю 2^10 и по модулю 5^10,

Обратите внимание, что в следующем коде магия ценности u2 а также u5 были найдены с помощью Расширенный евклидов алгоритм. Вам не нужно программировать этот алгоритм самостоятельно, потому что эти значения являются константами. я использую максима И его gcdex функция, чтобы вычислить их.

Вот модифицированная версия:

typedef unsigned long long ull;

ull const M  = 10000000000ull;

ull pow_mod10_10(ull n, ull p) {
ull const m2 = 1024;    // 2^10
ull const m5 = 9765625; // 5^10
ull const M2 = 9765625; // 5^10 = M / m2
ull const M5 = 1024;    // 2^10 = M / m5
ull const u2 = 841;     // u2*M2 = 1 mod m2
ull const u5 = 1745224; // u5*M5 = 1 mod m5

ull b2 = 1;
ull b5 = 1;
ull n2 = n % m2;
ull n5 = n % m5;

while(p) {
if(p%2 == 1) {
b2 = (b2*n2)%m2;
b5 = (b5*n5)%m5;
}
n2 = (n2*n2)%m2;
n5 = (n5*n5)%m5;
p /= 2;
}

ull np = (((b2*u2)%M)*M2)%M;
np    += (((b5*u5)%M)*M5)%M;
np    %= M;
return np;
}

3