逆元

· · 个人记录

定义

那么我们在取模的意义下，除法就可以转为乘法啦~ ## 求法 ### 1)费马小定理（$p$是质数时才可用） > 如果$p$是一个**质数**，而整数$a$不是$p$的倍数，则有$a^{p-1}\equiv1 \pmod {p}

那么a\times a^{p-2}\equiv1\pmod {p}

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

快速幂求 a^{p-2}\pmod {p}即可

没说它是质数，肯定不能用

2)扩展欧几里得

> 对于三个自然数 $a,b,c$ ，求解 $a\times x + b\times y = c$ 的 $(x,y)$ 的整数解。 那么逆元就是$x$在$a\times x + b\times y = 1$ 中的$[1,p-1]$的解 所以只要知道$x$的值就好啦，且为了使$x$在$[1,p-1]$中，最后要`(x%p+p)%p` ### [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082) ## 题目描述 求关于$ x$的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。输入数据保证一定有解。 $2 ≤a, b≤ 2,000,000,000$。 ```cpp #include<bits/stdc++.h> using namespace std; int Exgcd(int a,int b,int &x,int &y){ if(!b){ x=1; y=0; return a; } int d=Exgcd(b,a%b,y,x); y-=(a/b)*x; return d; } int main(){ int a,b,x,y; scanf("%d%d",&a,&b); int d=Exgcd(a,b,x,y); printf("%d\n",(x%b+b)%b); } ``` ### 3）欧拉定理求逆元 $\tiny 不认识\varphi(p)？$看[这里](https://www.luogu.com.cn/blog/205125/shuo-lun-han-shuo) >当 $a,m\in \mathbb{Z}$，且 $\gcd(a,m)=1$ 时有 $a^{\varphi(m)}\equiv 1\pmod{m}

那么a\times a^{\varphi(p)-1}\equiv 1\pmod{p}

x\equiv a^{\varphi(p)-1}\pmod {p}

快速幂求 a^{\varphi(p)-1}\pmod {p}即可

4）线性求逆元

令\left\lfloor \dfrac{p}{i} \right\rfloor* i+r=p

\left\lfloor \dfrac{p}{i} \right\rfloor* i+r \equiv 0 \pmod p

同时乘以 i^{-1}和r^{-1}

\left\lfloor \dfrac{p}{i} \right\rfloor* r^{-1}+i^{-1} \equiv 0 \pmod p i^{-1} \equiv -\left\lfloor \dfrac{p}{i} \right\rfloor* r^{-1} \pmod p i^{-1} \equiv p-\left\lfloor \dfrac{p}{i} \right\rfloor* r^{-1} \pmod p

因为r=p-\left\lfloor \dfrac{p}{i} \right\rfloor * i

那么r=p\% i

inv[1]=1 \\inv[i]=((p-\left\lfloor \dfrac{p}{i} \right\rfloor)* inv[p\% i])\%p (2\leqslant i< p) \end{cases}

P3811 【模板】乘法逆元

给定 n,p 求 1\sim n 中所有整数在模 p 意义下的乘法逆元。

这里 a 模 p 的乘法逆元定义为 ax\equiv1\pmod {p} 的解。

1 \leq n \leq 3 \times 10 ^ 6, n < p < 20000528

输入保证 p 为质数。

#include<bits/stdc++.h>
using namespace std;
long long inv[3000005];
int main(){
    int n,p;
    scanf("%d%d",&n,&p);
    inv[1]=1;
    printf("1\n");
    for(int i=2;i<=n;i++)
        inv[i]=((p-p/i)*inv[p%i])%p,printf("%lld\n",inv[i]);
}