费马小定理优化优化多数的乘方

要求

a^b^c mod p

保证gcd(c,p)=1

用费马小定理

b:=quick_mod(b,c,p-1);

c:=quick_mod(a,b,p);

a^c mod p=a^(c mod phi(p)) mod p

而素数的phi函数是无需计算的，即p-1

推广到多个，依次降幂即可。不断应用快速幂。

 

var a,b,c,p,ans:int64;

function quickmod(a,b,p:int64):int64;
var ret:int64;
begin
      ret:=1;
      a:=a mod p;
      while b<>0 do
        begin
          if (b and 1)=1 then ret:=ret*a mod m;
          b:=b>>1;
          a:=a*a mod m;
        end;
      exit(ret);
end;

begin
      read(a,b,c,p);
      b:=quickmod(b,c,p-1);
      ans:=quickmod(a,b,m);
      writeln(ans);
end.