python - C++ 中的长数字

Question

我有这个 Python 程序:

# ...
print 2 ** (int(input())-1) % 1000000007

问题是这个程序在大数上工作了很长时间。我用 C++ 重写了我的代码，但有时我的答案是错误的。例如，在数字 12345678 的 Python 代码中，我得到了 749037894 并且它是正确的，但在 C++ 中，我得到了 -291172004。

这是C++代码:

#include <iostream>
#include <cmath>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    // ...
    long long x;
    cin >> x;
    long long a =pow(2, (x-1));
    cout << a % MOD;
}

Answer 1

如前所述，您的问题是对于大指数，您有整数溢出。

要克服这个问题，请记住模乘法具有这样的特性:

(A * B) mod C = (A mod C * B mod C) mod C

然后您可以使用快速求幂方案实现“e 的幂 p 模 m”函数。 假设没有负权力:

long long powmod(long long e, long long p, long long m){
    if (p == 0){
        return 1;
    }
    long long a = 1;
    while (p > 1){
        if (p % 2 == 0){
            e = (e * e) % m;
            p /= 2;
        } else{
            a = (a * e) % m;
            e = (e * e) % m;
            p = (p - 1) / 2;
        }
    }
    return (a * e) % m;
}

请注意，每次乘法后都会取余数，因此不会发生溢出，如果单次乘法不溢出(1000000007 为 m 和 long long).