「学习笔记」乘法逆元

· · 个人记录

逆元定义

若 ax\equiv 1\pmod p 且 a 与 p 互质，那么定义 x 是 a 的逆元，记为 a^{-1}，也可称 x 是 a 在 \text{mod}\ p 意义下的倒数

求解方法

求解逆元有下列三种方法：

扩展欧几里得

P1082 同余方程

将同余方程 ax\equiv 1\pmod p 转化为 ax+by=1 利用扩欧求解，单个查找效率为 O(\log n)

```cpp ll a,p,x,y; void ex_gcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0; return; } ex_gcd(b,a%b,x,y); ll tmp=x; x=y; y=tmp-a/b*y; } int main(){ cin>>a>>p; ex_gcd(a,p,x,y); x=(x%p+p)%p; cout<<x<<"\n"; return 0; } ``` [「学习笔记」扩展欧几里得](https://www.luogu.com.cn/blog/LiBoyi/post-xue-xi-bi-ji-kuo-zhan-ou-ji-li-dei) ### 费马小定理 **费马小定理**的内容是 > 若 $p$ 为素数，$a\in N^{*}$，且 $a,p$ 互质，则有 $a^{p-1}\equiv 1\pmod p

代入有 ax\equiv a^{p-1}\pmod p

\ \ \ \ \ \ \ \ \ \ \ \ \ x\equiv a^{p-2}\pmod p

利用快速幂算出 a^{p-2}\pmod p 即可

ll a,p,x;
ll fpm(ll x,ll power,ll mod){
    x%=mod;
    ll res=1;
    while(power){
        if(power&1) res=(res*x)%mod;
        x=(x*x)%mod;
        power>>=1;
    }
    return res;
}
int main(){
    cin>>a>>p;
    x=fpm(a,p-2,p);
    cout<<x<<"\n";
    return 0;
}

线性递推

这个算法用于求一连串数字对一个 p 的逆元，时间复杂度为 O(n)

首先有 1^{-1}\equiv 1\pmod p

然后设 p=k\times i+r\ \ \ (1<r<i<p) 即 k 是 p/i 的商，r 是余数

将这个式子放在 \mod p 意义下就有

k\times i+r=0\pmod p

乘上 i^{-1} 和 r^{-1} 有

k\times r^{-1}+i^{-1}=0\pmod p i^{-1}=-k\times r^{-1}\pmod p

又有 k=[\frac{p}{i}]，r=p\ \text{mod}\ i ，则

i^{-1}=-[\frac{p}{i}]\times (p\ \text{mod}\ i)^{-1}\pmod p

因为 p\ \text{mod}\ i<i，能得出 (p\ \text{mod}\ i)^{-1}>i^{-1}，所以在求出 i^{-1} 之前早已求出 (p\ \text{mod}\ i)^{-1}

因此用数组 inv[i] 记录 i^{-1}，有

inv[i]=-p/i\times inv[p\ \text{mod}\ i]\ \text{mod}\ p

要保证 i^{-1}>0，所以再加上 p\ (p\ \text{mod}\ p=0)，即

inv[i]=(p-p/i)\times inv[p\ \text{mod}\ i]\ \text{mod}\ p

显然有 inv[1]=1

ll a,p,inv[maxn];
int main(){
    cin>>a>>p;
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(p-(p/i))*inv[p%i]%p;
        cout<<inv[i]<<"\n";
    }
}

P3811 【模板】乘法逆元