如何避免快速模幂溢出

我想解决一个关于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因为溢出。我怎样才能避免溢出？

来源

2013-07-29 jyotesh

我不认为它是可以避免的，除非你彻底改变了实现。 – 0decimal0

更好的使用大数字库，像gmp libmp ... – mathk

int64 * int64的结果需要int128 – BLUEPIXY

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

来源

2013-07-29 10:34:24 Henrik

+1我测试了这个，它给了我与Python中的pow（2,249999999997,9999999999989）'相同的结果。 –

-1

您可以使用无符号长长代替长长，它会帮助你数值越高，其范围是0到18,446,744,073,709,551,615玩。

来源

2013-07-29 10:11:33 Mahesh

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

来源

2013-07-29 12:01:17

如何避免快速模幂溢出

回答

相关问题