逆元模板

本文最后更新于：4 years ago

1.费马小定理

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
const ll mod=998244353;
inline ll qpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
//a的逆元 = qpow(a,mod-2)

2.扩展欧几里得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef long long ll;
const ll mod=998244353;
inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}
inline ll inv(ll a){
    ll x,y;
    ll d=exgcd(a,mod,x,y);
    if(d==1){
        return (x%mod+mod)%mod;
    }
    return -1;
}
//a的逆元的inv(a)
formwork 模板

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！