指数爆炸的时候就要降幂

就是求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 }