快速幂与逆元

先上快速幂板子：

#define int long long 

int fast_power(int x,int y,int mod){
    int res=1;
    while(y){
        if(y&1) res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}

求逆元有两中办法

1.费马小定理

结论 ：快速幂中传入 a,mod-2,mod

2.扩展欧几里得

ll exgced(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll res=exgced(b,a%b,x,y);
    ll z=x;
    x=y;
    y=z-a/b*y;
    return res;
}