范围10 ^ 18的大模型算法？

Question

我必须计算N ^ X MOD 10 ^ 18 + 7,我的范围是1 <= N,X <= 10 ^ 18.通常的大模型算法将无法计算这一点.什么是解决这个问题的正确算法我正在使用C++.当范围是10 ^ 18时,10 ^ 18 + 7的最低mod将是10 ^ 18,如果是这样,那么编译器将必须计算10 ^ 18*10 ^ 18.这将导致溢出.

Answer 1

有一种解决方案不涉及使用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;
}