我使用下面的函数来计算的大数字模M，其中M为任意整数，即权力（一^ B）％M
long long power(long long x, long long y, long long p)
{
long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res*x) % p;
// y must be even now
y = y>>1; // y = y/2
x = (x*x) % p;
}
return res;
}
但是，对于一些数字连这个功能无法正常工作。 例如，如果我叫
power(1000000000000,9897,52718071807);
我得到一个负数作为输出。 这是因为以下原因：有一个在电力功能的线路：
x = (x*x) % p;
当x是大的，我们说X = 46175307575，存放在X执行X =（X * X）％P变为负值后的值。 我不明白为什么会发生。 即使（X * X）的值越过长长整型的上范围，我没有在任何地方存储其值，我只存储（X * X）％P，其值0之间应该处于至p。 此外，由于p没有穿过长长的范围，请问X交呢？ 为什么会出现此问题，以及如何解决这个问题请告诉我。
在GeeksForGeeks是这样的功能：
// Returns (a * b) % mod
long long moduloMultiplication(long long a,
long long b,
long long mod)
{
long long res = 0; // Initialize result
// Update a if it is more than
// or equal to mod
a %= mod;
while (b)
{
// If b is odd, add a with result
if (b & 1)
res = (res + a) % mod;
// Here we assume that doing 2*a
// doesn't cause overflow
a = (2 * a) % mod;
b >>= 1; // b = b / 2
}
return res;
}
用它代替
x = (x*x) % p;
即
x = moduloMultiplication(x, x, p);
和代替
res = (res*x) % p
即
res = moduloMultiplication(res, x, p);
欢迎有符号整数溢出和未定义的行为 （UB）。
我只是存储（X * X）％P，其数值介于0应该骗页。
这是不正确。 x*x可能会溢出long long的数学和结果是UB。 @Osiris 。 样品UB包括一个产品，是具有正操作数负..
some_negative_value % some_positive_p结果为负的值。 - 见参考文献 。 这是范围外[0...p)
解决的办法是不溢出符号整数运算。
一个简单的第一步是使用无符号整数运算。
没有溢出问题的全方位的解决方案是在这里没有范围限制模幂
注意OP的代码也没有一个角落的情况： power(some_x, 0, 1)因为它时，预计0返回1。
// Fix
// long long res = 1;
long long res = 1%p;
// or
long long res = p != 1;
除了由@Doug居里提到的解决方案，还可以使用128个比特的数据类型__int128 。
long long pow(long long a, long long b, long long mod)
{
__int128 res = 1;
while(b > 0)
{
if(b&1)
{
res = (res*a);
res = res%mod;
}
b = b>>1;
a = ((__int128)a*a)%mod;
}
return res;
}
如果国防部==（2 ^ 63-1），则该解决方案将无法工作。
解决方案：国防部<= 2 ^ 62
（P-1）*（P-1）> 2 ^ 63。 所以就会出现溢出。 您需要实现与模乘法。
试试这个：
long long multiply(long long a,long long b,long long m){
if(b == 0){
return 0;
}
if(b==1){
return a%m;
}
if(b&1){
return ((a%m)+multiply(a,b-1,m))%m;
}
long long x = multiply(a,b>>1,m);
return multiply(x,2,m);
}
long long bigmod(long long a,long long b, long long m){
if(b == 0){
return 1;
}
if(b == 1){
return a%m;
}
if(b & 1){
return multiply(a%m,bigmod(a,b-1,m),m);
}
long long x = bigmod(a,b>>1,m);
return multiply(x,x,m);
}
