## 乘法逆元小结
https://www.freesion.com/article/43361201366/

乘法逆元，一般用于求
$$\large \frac{a}{b} \ \ \ (mod \  \ p)$$
的值，($p$通常为质数),是解决模意义下分数数值的必要手段。

### 一、逆元定义
<center><img src='https://www.freesion.com/images/942/0ff480d6440f4723342f4c094b9abde6.png'></center>

很明显，上述式子只有一条不成立，即 $(a/b) \% p$，但是在有些情况下，又需要进行有模运算的除法。因为式子不成立，如果 $a$ 过大或者 $b$ 过大，极易导致计算过程丢失精度，造成结果误差。因此，为了杜绝这一现象，**逆元**出现了。


> 若$a\times x \equiv 1 (mod \  b)$，且$a$与$b$互质，那么我们就能定义：

> $x$为$a$的逆元,记为$a^{-1}$,所以我们也可以称$x$为$a$在$mod \ b$意义下的**倒数**。

> 所以对于 $\frac{a}{b}\ (mod \ p)$ ，我们就可以求出$b$ 在 $mod \ p$ 下的逆元，然后乘上 $a$ ，再 $mod \ p$，就是这个分数的值了。

### 二、求解逆元的方式


#### 1、费马小定理+快速幂求逆元(p一定要质数)

**费马小定理**
> 若$p$为素数，$a$为正整数，且$a、p$互质。则有$a^{p−1}≡1(mod \ p)$。

这个我们就可以发现它这个式子右边刚好为 $1$ 。

所以我们就可以放入原式，就可以得到：
$$\large a \times x \equiv 1 (mod \ \ p )$$
$$\large a \times x \equiv a^{p-1} (mod \ \ p ) $$
$$\large x \equiv a^{p-2} (mod \ \ p )$$

所以我们可以用快速幂来算出 $a^{p−2}(mod \ p)$的值，这个数就是它的逆元了

代码也很简单：
```c++
typedef long long LL;
LL qmi(LL a, LL k, LL p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int main() {
    int a, p;
    cin >> a >> p;
    LL x = qmi(a, p - 2, p); // x为a在mod p意义下的逆元
    return 0;
}
```
#### 2、欧拉定理求逆元(相当于费马小定理的扩展)
解法一的拓展:欧拉定理+快速幂求逆元($p$不一定为质数,但$a$ $p$还是要互质)
一般不用这种办法，因为它能干的，扩展欧几里得都能干！
<font color='red'><b>略</b></font>

#### 3、扩展欧几里得
**注意：($p$不用为质数但$a,p$要互质，不然$a^{-1}$无解)**

这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于 $mod \ p$ 比较大的时候)。

这个就是利用拓欧求解 线性同余方程 $a∗x≡c(mod \ b)$ 的$c=1$的情况。我们就可以转化为解 $a∗x+b∗y=1$ 这个方程。

求解这个方程的解。不会拓欧可以点[这里](https://www.cnblogs.com/zjp-shadow/p/9267675.html#autoid-3-3-0)~

而且这个做法还有个好处在于，当 $a⊥p$ （互质），但 $p$ 不是质数的时候也可以使用。

代码比较简单：
```c++
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    LL x, y;
    exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}
```

#### 4、递推打表
用于求一连串数字对于一个$mod \ p$的逆元。 [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811)
对于一个区间的逆元，只能用这种方法，别的算法都比这个要慢。

$O(n)$筛$1$到$n$所有数模$p$的逆元：
* 初值$\large Inv[1]=1$
* 设$\large p=ki+r$,则 $\large ki+r \equiv 0 (mod \ p)$
* 两边同乘$\large i^{-1}r^{-1}$,得$\large kr^{-1}+i^{-1} \equiv 0 (mod \ p)$
* 移项：$\large i^{-1} \equiv -kr^{-1} (mod \ \ p )$
* $\large k=\left \lfloor \frac{p}{i} \right \rfloor$,所以$-k \equiv p- \frac{p}{i} (mod \ \ p ) $
* 所以`Inv[i]=(p-p/i)*Inv[p%i]%p`
  

### 三、阶乘逆元 [挖坑待填]
线性求阶乘的逆元
设第$x$项阶乘为$x!$,其逆元为$x!^{-1}$,那么有递推式:$\large \displaystyle (x-1)^{-1} = (x!)^{-1}*x$
所以从后往前递推求。

https://blog.csdn.net/qq_52142857/article/details/121032531

https://www.bbsmax.com/A/xl56Pb97zr/

https://blog.csdn.net/kiwi_berrys/article/details/54834977

https://www.freesion.com/article/43361201366/#4__191