求解模意义下的乘法逆元是算法竞赛中的重要内容，通常用于解决模意义下的分数数值表示或者模意义下的除法，本文试图通过扩展欧几里得、费马小定理和欧拉定理、递推、阶乘递推等算法求解乘法逆元。
1 定义
1.1 同余
若对整数a,b满足，m|(a-b)，则称a,b在模m意义下同余，记为a \equiv b，容易验证同余是一个等价关系。
1.2 乘法逆元
若ax \equiv 1 \pmod p，则称x为模p意义下a的乘法逆元，记为a^{-1}。
2 性质
2.1 存在性
ax \equiv 1 \pmod p中x存在当且仅当(a,p)=1
证明：
(\Rightarrow )
若(a,p) = 1，由Bezout定理，\exist x,y \; s.t \; ax+py=(a,p)=1，故ax\equiv 1\pmod p，由此亦知x不唯一
(\Leftarrow )
若ax \equiv 1 \pmod p，则\exist y \; s.t. \; ax-1=py\iff ax-py=1\iff (a,p)=1
特别地，当p为质数，a不为p的倍数时一定有解，该特例说明模p的等价类可以构成一个域。
2.2 加法与乘法的诱导
容易验证可诱导整数上的加法与乘法到等价关系上，我们有：
(a+b)\bmod p = a\bmod p + b\bmod p
(a\cdot b)\bmod p = a\bmod p \cdot b\bmod p
需要注意，并不存在\Large \left[ \frac{a}{b} \right] \bmod p = \left[ \frac{a \bmod p}{b \bmod p} \right]
3 算法实现
洛谷 P3381 【模板】乘法逆元
对于该题目而言并不是所有算法均适合。
3.1 扩展欧几里得算法（Extended Euclidean Algorithm）
3.1.1 思路
对于二元一次不定方程ax+by=(a,b)，由扩欧算法可以求出其中一个解。则可将同余方程ax \equiv 1 \pmod p归结到二元一次不定方程ax+py=1，解存在的条件见上文。
需要注意：该方法只要求(a,p)=1
时间复杂度：O(\log (a+p))
3.2 费马小定理与欧拉定理
3.2.1 费马小定理（Fermat's Little Theorem）
若p为质数，a为正整数，且(a,p)=1，那么a^{p-1} \equiv 1\pmod p
需要注意，该定理的逆定理存在部分反例。
3.2.2 欧拉定理（Euler Theorem）
由于费马小定理要求p为质数，当p为合数时需要适用条件更广的欧拉定理。需要注意：由于欧拉函数求解时间复杂度并不低，这种方法并不常用仅作介绍。
欧拉函数定义：欧拉函数\phi (n)为小于等于n的正整数中与n互质的数的个数。
性质：若p为质数，则\phi (p) = p - 1，此情形即为费马小定理。
欧拉定理：a,p>0, (a,p)=1 \implies a^{\phi (p)} \equiv 1 \pmod p
3.2.3 思路
对于费马小定理，仅需通过快速幂直接解模p意义下a的p-1次方。
时间复杂度：O(\log p)
对于欧拉定理，需要先求解欧拉函数，再通过快速幂进行计算。
时间复杂度：O(\sqrt{p})
需要注意，该方法要求p为质数。
3.3 递推法
3.3.1 思路
首先显然1^{-1} \equiv 1 \pmod p，
不妨设最小正整数i使得a \equiv i \pmod p，p=ki+r \pmod p(1 < r < i < p)
在模p意义下有
ki+r \equiv 0 \pmod p
由前文叙述知i,r模p的乘法逆元存在，等式两边同乘i^{-1} r^{-1}后有
i^{-1} \equiv -kr^{-1} \pmod p
熟知k=\left[ \frac{p}{i} \right] , r=p \bmod i，
我们有i^{-1} \equiv -\left[ \frac{p}{i} \right] (p \bmod i)，
由于p \bmod i < p该算法可行，
若要得到最小整数解再魔改模p加p处理一下即可，则得到如下递推方程：
inv[i] = p - (p / i) * inv[p % i] % p时间复杂度：由于\large p \bmod i < \frac{i}{2}，时间复杂度为O(\log i)
需要注意，该方法要求p为质数。
3.4 阶乘递推法
第一次见这种骚操作
3.4.1 思路
首先计算出1~n所有数的阶乘
然后易证(i-1!)^{-1} \equiv ((i-1)!)^{-1} \cdot i \pmod p
最后i^{-1} \equiv (i!)^{-1} \cdot (i-1)! \pmod p
3.5 利用全积、前缀积和后缀积
又是没见过的骚操作
3.5.1
考虑求n个数a_{1} ...a_{n}的乘法逆元，对于其中的a_{x} ^{-1}
定义：
全积\Large p0 = \prod_{i=1} ^{n} ai
前缀积\Large p1 = \prod_{i=1} ^{x-1} ai
后缀积\Large p1 = \prod_{i=x+1} ^{n} ai
求出p0^{-1},p1,p2
那么由于a_{x} \cdot p1 \cdot p2 \equiv p0 \pmod p
则a_{x} ^{-1} \equiv p1 \cdot p2 \cdot p0^{-1}