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

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

未测试，但你明白了。只要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;
}