2024-03-28 11:30:42 发布
网友
我用Python编写了这个程序:
# ... print 2 ** (int(input())-1) % 1000000007
问题是这个程序在大数据上工作很长时间。我用C++重写了我的代码,但有时我的答案是错误的。例如,在Python代码中,对于数字^ {< CD1> },我得到了^ {CD2}},它是正确的,但是在C++中,我得到了^ {CD3}}。在
这是C++代码:
正如许多其他答案所提到的,你的问题在于整数溢出。在
您可以像deniss建议的那样,实现自己的modmul()和modpow()函数。在
但是,如果这是一个需要用非常大的数字进行大量计算的项目的一部分,我建议使用一个像GNU GMP或mbedTLS 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和{}),则不会发生溢出。在
1000000007
m
正如许多其他答案所提到的,你的问题在于整数溢出。在
您可以像deniss建议的那样,实现自己的modmul()和modpow()函数。在
但是,如果这是一个需要用非常大的数字进行大量计算的项目的一部分,我建议使用一个像GNU GMP或mbedTLS Bignum library这样的“大数库”。在
你似乎处理的是正数,而这些正是你为它们的存储分配的位数。还要记住,在计算负值的方式上,Python和C/C++之间存在差异。要获得类似的计算,您需要将模加到值中,使其为正,然后取模,这是Python中的工作方式:
在取模之前,你可能需要加上模n次直到临时值为正。在
如前所述,您的问题是对于大指数,存在整数溢出。在
要克服这一点,请记住模乘有这样的性质:
然后你就可以用快速求幂的方法实现“e到幂p模m”函数。 假设没有负幂:
请注意,余数是在每次乘法之后获得的,因此如果单个乘法不溢出(对于}),则不会发生溢出。在
1000000007
作为m
和{相关问题 更多 >
编程相关推荐