范围10^18的大模算法？

Question

我必须计算N^X MOD 10^18+7，我的范围是1<=N，X<=10^18。通常的大模块算法将无法计算这一点。用C++解决这个问题的正确算法是什么？当范围为10^18时，10^18+7的最低模数将为10^18，如果是，则编译器必须计算10^18*10^18。会导致溢出。

Answer 1

有一种解决方案不涉及使用bignum。这个简单的解决方案的主要问题是需要计算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;
}