c++ - 我如何计算bigmod(bigmod(a^n)-bigmod(b^m))？

Question

我要计算

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

但是a^n和b^m可能非常大

Bigmod(bigmod(a^n)-bigmod(b^m)) ?

我尝试计算bigmod(a^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);