范围 10^18 的大 mod 算法？

Question

我必须计算 N^X MOD 10^18+7 并且我的范围是 1<=N,X<=10^18 。通常的 big mod 算法将无法计算 this 。解决这个问题的正确算法是什么我正在使用 C++ 。由于范围是 10^18，10^18+7 的最低 mod 将是 10^18 ，如果是这样，那么编译器将不得不计算 10^18*10^18 。这将导致溢出。

Answer 1

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

范围 10^18 的大 mod 算法？

Big mod algorithm for range 10^18?

c++

algorithm

number-theory