多种求逆元的方法（递推，费马小定理，exgcd）（附exgcd讲解）

逆元简介：

已知 $a,b\left(gcd\right(a,b)=1)$a,b(gcd(a,b)=1)对于
$a\ast x\equiv 1\left(modb\right)$a∗x≡1(mod b)
我们称 $x$x 为 $a$a 模 $b$b 意义下的逆元， 记做 $a^{-1}$a−1，逆元常常用于模意义下的除法。

引理： $a$a 在 $(0,b]$(0,b] 的逆元 $x$x 唯一

证明

反证法：设 $y$y也为 $a$a的逆元 $(0\&lt;y\&lt;b)$(0<y<b), 即 $a\ast y\equiv 1\left(modb\right)$a∗y≡1(mod  b)，不妨令 $y\&gt;x$y>x，
于是有 $a\ast (y-x)\equiv 0\left(modb\right)$a∗(y−x)≡0(mod  b)，因为 $gcd(a,b)=1$gcd(a,b)=1，于是 $b\mid (y-x)$b ∣ (y−x)，而 $y-x\&lt;b$y−x<b，不可能为b的倍数，因此矛盾。引理得证。

方法一：递推法 （求1~n的逆元）

求 $i\in [1,b)$i∈[1,b)每个数 $i$i模 $b$b 的逆元
记 $b=p\ast i+q(p=\lfloor \frac{b}{i}\rfloor ,q=bmodi)$b=p∗i+q(p=⌊ib​⌋,q=b mod i)，于是有
$p\ast i+q\equiv 0\left(modb\right)\Rightarrow p\ast q^{-1}+i^{-1}\equiv 0\left(modb\right)\Rightarrow i^{-1}\equiv -p\ast q^{-1}\left(modb\right)$p∗i+q≡0(mod  b)⇒p∗q−1+i−1≡0(mod  b)⇒i−1≡−p∗q−1(mod  b)
而 $q$q是小于 $i$i的，于是可以递推。

代码如下：

#include <cstdio>
#define LL long long
#define N 3000005
LL inv[N];
int main(){
	int i, j, n, p;
	scanf("%d%d", &n, &p);
	for(inv[1] = 1, i = 2; i <= n; i++){
		inv[i] = (p - p / i) * inv[p % i] % p;
	}
	for(i = 1; i <= n; i++) printf("%lld\n", inv[i]);
	return 0;
}

方法二：费马小定理（很常用，但模数必须是质数）

由费马小定理 $a^{p-1}\equiv 1\left(modp\right)\Rightarrow a^{p-2}\equiv a^{-1}\left(modp\right)$ap − 1≡1(mod  p)⇒ap − 2≡a−1(mod  p)
直接快速幂就完事儿辣。

代码如下：

#include <cstdio>
#define mod 1000000007
#define LL long long
LL ksm(LL a, LL b, LL p){
	LL s = 1;
	while(b){
		if(b & 1) s = s * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return s;
} 
int main(){
	LL a;
	scanf("%lld", &a);
	printf("%lld", ksm(a, mod-2, mod));
	return 0;
}

方法三：exgcd（拓展欧几里得，对模数无要求）

先贴波求 $gcd$gcd 的代码

int gcd(int a, int b){
	return !b? a: gcd(b, a%b);
}

拓欧本来是用于求关于 $a,b$a,b的不定方程 $ax+by=1$ax+by=1的解 $x，y$x，y。为什么可以用拓欧求逆元呢？
事实上，根据 $ax\equiv 1\left(modb\right)$ax≡1(mod  b)
我们可以得到 $b\mid (ax-1)\Rightarrow ax-1=by\Rightarrow ax+by=1（这里调了y的正负）$b∣(ax−1)⇒ax−1=by⇒ax+by=1（这里调了y的正负）
于是我们求 $a$a的逆元，等价于求该不定方程的解 $x$x， $x\in (0,b)$x∈(0,b)。
下面讲讲exgcd的原理 $ax+by=1令a=pb+q,p=\lfloor \frac{a}{b}\rfloor ,q=amodb$ax+by=1令a=pb+q,p=⌊ba​⌋,q=a mod b代入原式化简可得 $b\ast (px+y)+q\ast x=1$b∗(px+y)+q∗x=1,记 $x^{\prime }=px+y,y^{\prime }=x$x′=px+y,y′=x，可得 $b\ast x^{\prime }+\left(amodb\right)\ast y^{\prime }=1$b∗x′+(a mod b)∗y′=1
得到了结构一样的方程，如果我们能解出新方程的根，原方程也得解。于是我们一直迭代下去，有没有发现这就是gcd的过程呢？一直到y’的系数为0，此时 $a^{\prime }$a′就是最大公因数，为1。
我们令 $x^{\prime }=1,y^{\prime }=0$x′=1,y′=0，回溯回去就可以啦。

下面贴代码：

#include <cstdio>
void exgcd(int a, int b, int &x, int &y){
	if(!b) x = 1, y = 0;
	else{
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
int main(){
	int a, b, x, y;
	scanf("%d%d", &a, &b);
	exgcd(a, b, x, y);
	printf("%d", (x % b + b) % b);
	return 0;
} 

ps:码得好累，求支持啊！！