c - 如何避免快速模幂运算中的溢出

Question

我正在尝试解决需要模幂运算的 SPOJ 问题。我正在使用以下 C 代码

long long modpow(long long a,long long b,long long mod)
{
    long long product,pseq;
    product=1
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=(product*pseq)%mod;
        pseq=(pseq*pseq)%mod;
        b>>=1
    }
    return product;
}

问题是当我想计算时，它会因为溢出(2^249999999997)%999999999989而给出答案。0如何避免溢出？

Answer 1

Untestet，但你明白了。只要2*mod小于最大可表示long long值并且a、b和mod为正，这应该可以工作。

long long modpow(long long a,long long b,long long mod)
{
    long long product,pseq;
    product=1;
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=modmult(product,pseq,mod);
        pseq=modmult(pseq,pseq,mod);
        b>>=1;
    }
    return product;
}

long long modmult(long long a,long long b,long long mod)
{
    if (a == 0 || b < mod / a)
        return (a*b)%mod;
    long long sum;
    sum = 0;
    while(b>0)
    {
        if(b&1)
            sum = (sum + a) % mod;
        a = (2*a) % mod;
        b>>=1;
    }
    return sum;
}

Answer 2

另一个建议是利用 999999999989 是素数这一事实。通过使用关系 (a^n) = a % n（其中 n 是素数），u 可以简化操作。

Answer 3

您可以使用unsigned long long代替long long，它将帮助您玩更高的值，其范围是 0 到 18,446,744,073,709,551,615。