首页 > 代码库 > 费马小定理优化优化多数的乘方
费马小定理优化优化多数的乘方
要求
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.
费马小定理优化优化多数的乘方
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。