欧拉函数 欧拉降幂 快速幂

欧拉函数 即求1到n-1内与n互质的数的个数

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;
}
 

欧拉降幂

当指数爆炸的时候就要降幂

就是求a^b mod c

可以转化为

然后是快速幂

ll quickpow(ll x,ll y,ll z)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%z;
        x=x*x%z;
        y>>=1;
    }
    return ans;
}