1

我正在使用以下函数来计算以 m 为模的大数的幂，其中 m 是任意整数，即 (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;
}

但是，对于某些数字，即使此功能也不起作用。例如，如果我打电话

 power(1000000000000,9897,52718071807);

我得到一个负数作为输出。发生这种情况的原因如下： 幂函数中有一行：

  x = (x*x) % p;

当 x 很大时，假设 x=46175307575，执行 x=(x * x)%p 后存储在 x 中的值变为负数。我不明白为什么会这样。即使 (x * x) 的值超过了 long long int 的上限，我也不会将其值存储在任何地方，我只是存储 (x*x)%p ，其值应介于 0 到 p 之间。此外，由于 p 不跨越长距离，x 如何跨越它？请告诉我为什么会出现这个问题以及如何解决这个问题。

4

4 回答 4

3

在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;

IE，

x = moduloMultiplication(x, x, p);

而不是

res = (res*x) % p

IE，

res = moduloMultiplication(res, x, p);
于 2018-08-05T14:55:39.953 回答
1

欢迎使用有符号整数溢出和未定义行为(UB)。

我只是存储 (x*x)%p ，其值应介于 0 到 p 之间。

这是不正确的。 x*x可能会溢出long long数学，结果是 UB。 @奥西里斯。示例 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;
于 2018-08-06T05:38:04.670 回答
0

除了@Doug Currie 提到的解决方案，您还可以使用 128 bits data type __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;
}
于 2018-08-05T21:56:57.233 回答
0

如果 Mod == (2^63-1) 则此解决方案将不起作用。

解决方案：Mod <= 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);
}
于 2018-08-05T15:01:22.793 回答