以C为模的大数的幂 [英] Power for big numbers modulo m in C
问题描述
我正在使用以下函数来计算以m为模的大数的幂,其中m是任何整数,即(a ^ b)%m
I am using the following function to compute powers of big numbers modulo m, where m is any integer,i.e. (a^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;
}
但是,对于某些数字,即使此功能也不起作用。例如,如果我呼叫
But, for some numbers even this function is not working. For example, if I call
power(1000000000000,9897,52718071807);
我得到一个负数作为输出。发生这种情况是由于以下原因:
幂函数中有一行:
I get a negative number as the output. It happens because of the following reason: There is a line in the power function:
x = (x*x) % p;
当x大时,假设x = 46175307575,执行x =( x * x)%p变为负数。我不明白为什么会这样。即使(x * x)的值超过了long long int的上限,我也不会将其值存储在任何地方,而只是存储(x * x)%p,其值应介于0到p之间。另外,由于p没有跨过长距离,x会如何交叉呢?请告诉我为什么会出现此问题以及如何解决此问题。
When x is big, let's say x=46175307575, the value stored in x after executing x=(x * x)%p becomes negative. I don't understand why it happens. Even if the value of (x * x) crosses the upper range of long long int, I am not storing its value anywhere, I am just storing (x*x)%p whose value should lie between 0 to p. Also, since p doesn't crosses the long long range, how does x cross it? Please tell me why this problem occurs and how to solve this.
推荐答案
在 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);
这篇关于以C为模的大数的幂的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!