指数爆炸的时候就要降幂
就是求a^b mod c
可以转化为
a^(b mod phi?+phi?) mod c
phi 为 欧拉函数
欧拉函数phi(n)的求法：
1 ll phi(ll n) 2 { 3 ll i,rea=n; 4 for(i=2;i*i<=n;i++) 5 { 6 if(n%i==0) 7 { 8 rea=rea-rea/i; 9 while(n%i==0) 10 n/=i; 11 } 12 } 13 if(n>1) 14 rea=rea-rea/n; 15 return rea; 16 }
原文：https://www.cnblogs.com/xyq0220/p/10402964.html