我如何計算bigmod（bigmod（a^n）-bigmod（b^m））？

Question

我想計算

（一個^ N％K - B^M％K）％K

但是一個^ N和b^M可以非常大

Bigmod（bigmod（a^n）-bigmod（b^m））？

我試圖計算bigmod（一^ N） - bigmod（B^M），然後使用bigmod爲相減的結果，然後我意識到它給了一個錯誤的答案！ 有沒有什麼計算呢？

#include<cstdio> 
using namespace std; 

template<class T>T big_mod(T n,T p,T m) 
    { 
    if(p==0) 
     return (T)1; 
     T x=big_mod(n,p/2,m); 
     x=(x*x)%m; 
     if(p&1) 
      x=(x*n)%m; 
      return x; 
    } 

int main() 
{ 
    long long int a=37,b=26,m=10,n=20,mod=1000000008,x,y,z; 
    x=big_mod(a,m,mod); 
    y=big_mod(b,n,mod); 
    z=((x%mod-y%mod)%mod); 
    cout<<z; 
} 

Answer 1

How can i calculate bigmod(bigmod(a^n)-bigmod(b^m)) ? 

讓你的模量是k。

((a^n) % k - (b^m) % k + k) % k 

您需要添加k因爲減法會導致負面的結果：你的表情是相當的。這將使其正面，而不會影響結果，因爲k % k == 0。

爲了計算(x^y) % k，由平方算法使用冪，並確保你拿模在每一個步驟：

x^y % k = ((x^(y/2))^2) % k if y is even 
      (x*x^(y - 1)) % k else 

爲您的代碼，假定其他一切工作，你只需要改變這一行：

z=((x%mod-y%mod)%mod); 

這樣：

z=((x%mod-y%mod+mod)%mod);