求逆元

2023/6/26 算法竞赛 C++ 数论 逆元

一般求逆元有三种方法：扩欧、快速幂、递推

扩展欧几里得求逆元

a ⋅ x ≡ b mod  m 等价于 ax + cm = b

由扩展欧几里得解丢番图方程可以得到逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll mod_inverse(ll a,ll m)
{
    ll x,y;
    exgcd(a,m,x,y);
    return (x%m+m)%m;
}

快速幂求逆元

由费马小定理， ap − 2 就是 a 在模 p 意义下的逆元

1
2
3
4
ll mod_inverse(ll a,ll m)
{
    return fast_pow(a,m-2,m);
}

递推求逆元

对于 i−1 ，设 p = ki + j

有 ki + j ≡ 0 mod  p , 即 kj−1 + i−1 ≡ 0 mod  p

1
2
3
4
5
6
7
8
9
int inv[N];
void mod_inverse(ll n,ll p)
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    }
}
img_show