C++中的长数

2024-03-28 11:30:42 发布

您现在位置:Python中文网/ 问答频道 /正文

我用Python编写了这个程序:

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

问题是这个程序在大数据上工作很长时间。我用C++重写了我的代码,但有时我的答案是错误的。例如,在Python代码中,对于数字^ {< CD1> },我得到了^ {CD2}},它是正确的,但是在C++中,我得到了^ {CD3}}。在

这是C++代码:

^{pr2}$

Tags: 数据答案代码程序input错误数字int
3条回答

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

您可以像deniss建议的那样,实现自己的modmul()和modpow()函数。在

但是,如果这是一个需要用非常大的数字进行大量计算的项目的一部分,我建议使用一个像GNU GMPmbedTLS Bignum library这样的“大数库”。在

你似乎处理的是正数,而这些正是你为它们的存储分配的位数。还要记住,在计算负值的方式上,Python和C/C++之间存在差异。要获得类似的计算,您需要将模加到值中,使其为正,然后取模,这是Python中的工作方式:

cout << (a+MOD) % MOD;

在取模之前,你可能需要加上模n次直到临时值为正。在

如前所述,您的问题是对于大指数,存在整数溢出。在

要克服这一点,请记住模乘有这样的性质:

(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和{}),则不会发生溢出。在

相关问题 更多 >