逆元模板

求逆元模板

递推求逆元

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

费马小定理求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}