欧拉降幂

一般对于 a^b%p 的形式当b很大，大到long long都存不小时，就不能直接快速幂了，必须对b取模，但不是直接让b对p取模，为什么呢？因为是错的。

这个时候我们怎么办呢？

这个时候我们就要用到欧拉降幂了。

上面就是欧拉降幂的公式，一般来说，我们使用第三个即可。

phi 就是欧拉函数。

下面给出求欧拉函数的板子

 ll phi(ll n)
{
     ll i,rea=n;
     for(i=2;i*i<=n;i++)
     {
         if(n%i==0)
         {
             rea=rea-rea/i;
             while(n%i==0)  n/=i;
          }
     }
     if(n>1)     rea=rea-rea/n;
     return rea;
}