逆元模板

求逆元模板

递推求逆元

int inv[maxn];
int inv[1] = 1;
rep(i,2,max){
    inv[i] = inv[mod%i]*(mod-mod/i)%mod;
}

费马小定理求逆元

ll extend_gcd(ll a,ll b,ll x,ll y){
    if(a==0 && b==0) return -1;
    if(b==0) {
        x = 1;y = 0;
        return a;
    }
    ll d = extend_gcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}
ll mod_reverse(ll a,ll n){
    ll x,y;
    ll d = extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}