我知道这个问题可能看起来很幼稚,但我已经在谷歌和这个网站上搜索了很多次,但都没有找到令人满意的答案。 我只是想计算(A*B)%MOD,假设a、b和MOD都是long long类型的。 假设MOD比A和B都大,以至于A%MOD = A且B%MOD = B,但A*B大于64位。如何正确地计算(A*B)%MOD的值?
我知道这个问题可能看起来很幼稚,但我已经在谷歌和这个网站上搜索了很多次,但都没有找到令人满意的答案。 我只是想计算(A*B)%MOD,假设a、b和MOD都是long long类型的。 假设MOD比A和B都大,以至于A%MOD = A且B%MOD = B,但A*B大于64位。如何正确地计算(A*B)%MOD的值?
这里的基本思路是首先定义一个不会溢出的addmod
函数,它利用了负数在算术中的特性。然后使用位运算来定义timesmod
函数。时间复杂度为O(N)
,其中N是使用的位数(在本例中为64位)。
#include <iostream>
using namespace std;
typedef long long BigInt; // must be signed, to detect overflow
BigInt A = 0x7fffffffffffff01;
BigInt B = 0x7fffffffffffff02;
BigInt M = 0x7fffffffffffff03;
// For simplicity it is assumed x, y, and m are all positive.
BigInt addmod( BigInt x, BigInt y, BigInt m )
{
x %= m;
y %= m;
BigInt sum = x-m+y; // -m <= sum < m-1
return sum < 0 ? sum + m : sum;
}
BigInt timesmod( BigInt x, BigInt y, BigInt m )
{
x %= m;
y %= m;
BigInt a = x < y ? x : y; // min
BigInt b = x < y ? y : x; // max
BigInt product = 0;
for (; a != 0; a >>= 1, b = addmod(b,b,m) )
if (a&1) product = addmod(product,b,m);
return product;
}
int main()
{
cout << "A = " << A << endl;
cout << "B = " << B << endl;
cout << "M = " << M << endl;
cout << "A*B mod M = " << timesmod(A,B,M) << endl;
return 0;
}
输出:
A = 9223372036854775553
B = 9223372036854775554
M = 9223372036854775555
A*B mod M = 2
这很容易确认,因为A=-2
且B=-1
mod M
。
注意:此代码未经过优化。
BigInt
,因此无法可靠地检测溢出(它会导致未定义的行为)。您需要使用无符号类型才能获得可靠的溢出行为。 - Chris DoddaddMod
函数以解决这个问题。 - Mattlong long int multiply(long long a, long long b, long long mod)
{
long long result;
if(b==0) return 0LL;
result = multiply(a,b>>1,mod);
result = (result+result)%mod;
if(b&1) result = (result+a)%mod;
return result;
}
- unrealsoul007multiply(0x7fffffffffffff01,0x7fffffffffffff02,0x7fffffffffffff03)
返回了-9223372036854711038
。你得到什么结果?(我认为答案应该是 2
。) - Matt我认为你可以将128位的乘积分成两部分(高64位和低64位),并对每个部分取模p。假设p
大约是4^k
,那么你可以通过将hi64 / (p>>k)
相除来大致计算出这个数字中有多少个p;这应该会给你大约k-1
位正确答案。从整个数字中减去这么多个p
,现在hi64
就少了大约k-1
位。再次进行此操作,但计算(hi64 << k-1) / (p >> k)
。然后再次进行此操作,计算(hi64 << k+k-2) / (p >> k)
。
另一个帖子建议使用Schrage的技巧,听起来更好,但我不理解它。希望那个帖子的作者回来并完成他的回答!