我如何计算 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);

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

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

c

c++

algorithm

math

number-theory