乘法逆元

定义：

对于正整数 $a$，$n$ ，如果 $ax \equiv 1(\bmod n)$，那么称 $x$ 的最小整数解为$a \bmod n$的逆元。

模运算性质：

$(a±b) \bmod p=(a \bmod p±b \bmod p) \bmod p$

$(a \cdot b) \bmod p=(a \bmod p \cdot b \bmod p) \bmod p$

但是是有缺陷的，

$\frac{a}{b}\pmod p$是否与$\frac{a \bmod p}{b \bmod p}$相等？显然不相等。

如何解决这个问题，考虑将除法转为乘法。

那就需要找到一个$b_{inv}$使得$\frac{a}{b} \bmod p= a \cdot b_{inv} \bmod p$，其实这个$b_{inv}$就是$b$在$\bmod p$意义下的乘法逆元。

性质：

设$\frac{a}{b} \equiv x(\bmod p)$ -------①

假设存在 $b_{inv}$ 满足$a \cdot b_{inv} \equiv x(\bmod p)$-------②

①②式两边同乘一个 $b$

得到

$a \equiv bx(\bmod p)$----- ③ 

$a \cdot b_{inv} \cdot b \equiv bx(\bmod p)$------④

根据模运算减法性质将两式相减得 $a(b_{inv} \cdot b -1) \equiv 0(\bmod p)$

因为我们在找$b$得乘法逆元，所以$a$的值任意，所以式子相当于$b_{inv} \cdot b -1 \equiv 0(\bmod p)$

即$b_{inv} \cdot b \equiv 1(\bmod p)$

因此我们只需要找到满足$b_{inv} \cdot b \equiv 1(\bmod p)$的数$b_{inv}$，就是 $b$ 在 $\bmod p$意义下的乘法逆元。

存在条件：

是否总存在一个$b_{inv}$使式子成立？

举个例子，$b=2，p=10$，此时$2 \cdot b_{inv} \equiv 1 (\bmod 10)$，显然不成立，所以逆元有存在条件。

由$b_{inv} \cdot b \equiv 1(\bmod p)$，我们设$b \cdot b_{inv} = kp+1$，设 $g$ 为 $gcd(b,p)$ 

那我们将原式拆解开得：$g \cdot b_1 \cdot b_{inv} = k \cdot g \cdot p_1 +1$，合并得 $g(b_1 \cdot b_{inv} - kp)=1$

因为我们在正整数范围内讨论这个问题，所以只能有$g=1$且 $b_1 \cdot b_{inv} - kp=1$

以上步骤均可逆，所以乘法逆元存在的条件是当且仅当 $b$，$p$ 互质。

求法：

Ⅰ.费马小定理

费马小定理：若 $p$ 是质数，则$b^{p-1} \equiv 1(\bmod p)$

我们可以将式子变形：$b \cdot b^{p-2} \equiv 1(\bmod p)$，所以 $b_{inv}=b^{p-2}$，结合快速幂模板可求解

int fast_pow(int a,int b,int mod){
	int res=1; a%=mod;
	while(b){
	    if(b&1) res=(res*a)%mod;
	    a=a*a%mod;b>>=1;
	}
	return res%mod;
}
int get(int b,int p){
     retrun fast_pow(b,p-2,p);
}

Ⅱ.扩展欧几里得算法

利用费马小定理有一个弊端，就是 $p$ 只能为质数。

扩展欧几里得算法：求$ax+by=gcd(a,b)$的一组 $x$，$y$.

则我们要凑出扩欧的形式，求$a$在$\bmod p$意义下的乘法逆元（改字母防止混淆）

$a \cdot a_{inv} \equiv 1(\bmod p)$

令 $a_{inv}$ 为扩欧的一组解，式子可以表示为$a \cdot a_{inv} + p \cdot y=gcd(a,p)$

因为$a$，$p$互质，所以$gcd(a,p)=1$，所以:

$a \cdot a_{inv} + p \cdot y=1=gcd(a,p)$

int exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return a;}
	int r=exgcd(b,a%b,x,y);
	int t=x; x=y; y=t-a/b*y;
	return r;
}
int get(int a,int p){
    int x,y;int ret=exgcd(a,p,x,y);
    if(ret==1) return (x%p+p)%p;//防止出现负数
    else return -1; 
}

 Ⅲ.线性求逆元

前面两种有点慢，毕竟每个数都求了一遍逆元，复杂度是$log$级的。

如何求 $\left[ 1,n \right]$在$\bmod p$意义下的逆元？

保证$p$为质数，且$p>n$

对于一个数 $x$ ，由于 $p>x$ ，设$p=kx+r$，$k=\left[ \frac{p}{x} \right]$，$r= p \bmod x$。

在$\bmod p$ 意义下：

$kx+r \equiv 0(\bmod p)$

$kx \equiv -r(\bmod p)$

$k \cdot x \cdot r_{inv } \equiv -1 \equiv -x \cdot x_{inv }(mod p)$

$x_{inv }= -r_{inv } \cdot k(\bmod p)$

因为$r= p \bmod x < x$，如果我们按顺序依次求逆元，则 $r_{inv }$ 一定比 $x_{inv }$先求出。

若按上等式处理，得出的结果是负数，我们可以先$+p $ 再 $\bmod p$.

int inv[MAXN];
void init(){ inv[1]=1;
     for(int i=2;i<=n;i++){
	inv[i]=-(p/i)*inv[p%i];
	inv[i]=(inv[i]%p+p)%p;
     }
}

练习：

P3811 【模板】乘法逆元