如何避免快速模冪溢出

我想解決一個關於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

如何避免快速模冪溢出

回答

相關問題