Большой мод алгоритм для диапазона 10 ^ 18?
Я должен рассчитать N ^ X MOD 10 ^ 18 + 7 и мой диапазон 1<= Н, Х<= 10 ^ 18. Обычный алгоритм большого мода не сможет рассчитать это. Какой правильный алгоритм для решения этой проблемы
Я использую C ++. Поскольку диапазон равен 10 ^ 18, самый низкий мод 10 ^ 18 + 7 будет 10 ^ 18, если это так, то компилятор должен будет вычислить 10 ^ 18 * 10 ^ 18. что приведет к переполнению.
Решение
Есть решение, которое не предполагает использование bignums. Основная проблема с тривиальным решением — это необходимость вычисления n*n, Если n>sqrt(2^63-1) это переполнит int64 число. Решением этого является вычисление n*n%m так же, как вы вычисляете n^x%m,
Я имею в виду, что вам придется реализовать пользовательское модульное умножение, которое позволяет избежать переполнения, только делая дополнения.
В C ++ это было бы что-то вроде:
#include <iostream>
using namespace std;
template <typename T>
T mmul(T a, T b, T m) {
a %= m;
T result = 0;
while (b) {
if (b % 2) result = (result + a) % m;
a = (a + a) % m;
b /= 2;
}
return result;
}
template <typename T>
T mpow(T a, T b, T m) {
a %= m;
T result = 1;
while (b) {
if (b % 2) result = mmul(result, a, m);
a = mmul(a, a, m);
b /= 2;
}
return result;
}int main() {
long long big = 1000000000000000000;
cout << mpow(big+1, big+2, big+7) << endl;
}
Другие решения