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

您似乎在处理正数，而这些正数超出了您为其存储分配的位数。另请记住，Python 和 C/C++ 在对负值取模的计算方式上存在差异。要获得类似的计算，您需要将模数添加到该值，以便在您采用模数之前它是正数，这是它在 Python:

中的工作方式

cout << (a+MOD) % MOD;

您可能需要添加 MOD n 次直到临时值在取模之前为正数。

Answer 2

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

为了克服这个问题，请记住模乘法有这样的属性：

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

然后您可以使用快速求幂方案实现 'e to the power p modulo 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 也是如此） .

Answer 3

正如许多其他答案所提到的，您的问题在于整数溢出。

您可以按照 deniss 的建议进行操作，并实现您自己的 modmul() 和 modpow() 函数。

但是，如果这是需要对非常大的数字进行大量计算的项目的一部分，我建议使用 "big number library"，例如 GNU GMP or mbedTLS Bignum library。

Answer 4

在 C++ 中，各种基本类型都有固定的大小。例如 long long 通常是 64 位宽。但宽度因系统类型和其他因素而异。正如上面所建议的，您可以检查 climits.h 以了解您的特定环境的限制。

2 的 12345677 次方将涉及将二进制数 10 左移 12345676 位，这不适合 64 位 long long（我怀疑不太可能适合大多数long long 实施）。

另一个要考虑的因素是powreturns一个double（或long double）depending on the overload used。您没有说明您使用的是什么编译器，但很可能在将调用 pow 的结果分配给 long long 变量 a 时收到有关可能截断或数据丢失的警告。 =28=]

最后，即使 pow 返回一个 long double 我怀疑指数 12345677 太大而无法存储在 long double 中所以 pow 可能返回正无穷大然后被截断为适合 long long 的一些位模式。您当然可以通过引入一个中间 long double 变量来接收 pow 的值来检查，然后您可以在调试器中检查它。

C++ 中的长数字

Long numbers in C++

python

c++

math

long-integer