乘法逆元小结
乘法逆元，一般用于求
$frac{a}{b} pmod p$
的值（$p$ 通常为质数），是解决模意义下分数数值的必要手段。
一、逆元定义
若$a*xequiv1 pmod b$，且$a$与$b$互质，那么我们就能定义: $x$ 为 $a$ 的逆元，记为$a^{-1}$，所以我们也可以称 $x$ 为 $a$ 在$mod b$意义下的倒数，
所以对于 $displaystylefrac{a}{b} pmod p$ ，我们就可以求出 $b$ 在 $mod p$ 下的逆元，然后乘上 $a$ ，再 $mod p$，就是这个分数的值了。
二、求解逆元的方式
1.拓展欧几里得
条件 $a ot p$（互质），但 $p$ 不是质数的时候也可以使用。
这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于 $mod p$ 比较大的时候)。
这个就是利用拓欧求解 线性同余方程 $a*xequiv cpmod{b}$ 的$c=1$的情况。我们就可以转化为解 $a*x + b*y = 1$ 这个方程。
引理：$ax+by=c$有解的充分条件是$gcd(a,b)mid c$
所以$ax+by=gcd(a,b)①$显然有解
引理：$gcd(a,b)=gcd(b,a mod b)②$
将$①$代入$②$得
$ax_1+by_1=bx_2+(a mod b)y_2$
$ax_1+by_1=bx_2+(a-[frac{a}{b}]*b)y_2$
$ax_1+by_1=bx_2+ay-[frac{a}{b}]*by_2$
$ax_1+by_1=ay_2+b(x_2-[frac{a}{b}])$
$∴x_1=y_2,y_1=x_2-[frac{a}{b}]y$
$∵aot b$
$∴gcd(a,b)=1$
$∴当b=0时，a=1，此时有x=1，y的最小自然数解为0$
代码比较简单：
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 ", x); //x是a在mod p下的逆元 }
2.小费尔马定理（快速幂）
费马小定理：
若$p$为素数，$a$为正整数，且$a$、$p$互质。 则有$a^{p-1} equiv 1 (mod p)$。
这个我们就可以发现它这个式子右边刚好为 $1$ 。
所以我们就可以放入原式，就可以得到：
$a*xequiv 1 pmod p$
$a*xequiv a^{p-1} pmod p$
$x equiv a^{p-2} pmod p$
所以我们可以用快速幂来算出 $a^{p-2} pmod p$的值，这个数就是它的逆元了
代码也很简单：
ll fpm(ll x, ll power, ll mod) { x %= mod; ll ans = 1; for (; power; power >>= 1, (x *= x) %= mod) if(power & 1) (ans *= x) %= mod; return ans; } int main() { ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元 }
3.线性推逆元
用于求一连串数字对于一个$mod p$的逆元。洛谷P3811
只能用这种方法，别的算法都比这些要求一串要慢。
首先我们有一个,$1^{-1}equiv 1 pmod p$
然后设 $p=k*i+r,(1<r<i<p)$ 也就是 $k$ 是 $p / i$ 的商，$r$ 是余数 。
再将这个式子放到$pmod p$意义下就会得到：
$k*i+r equiv 0 pmod p$
然后乘上$i^{-1}$,$r^{-1}$就可以得到:
$k*r^{-1}+i^{-1}equiv 0 pmod p$
$i^{-1}equiv -k*r^{-1} pmod p$
$i^{-1}equiv -lfloor frac{p}{i} floor*(p mod i)^{-1} pmod p$
于是，我们就可以从前面推出当前的逆元了。
代码也很短：
inv[1] = 1; for(int i = 2; i < p; ++ i) inv[i] = (p - p / i) * inv[p % i] % p;
4.阶乘逆元 $O(n)$ 求
因为有如下一个递推关系。
$displaystyle inv[i+1]=frac{1}{(i+1)!}$
$displaystyle inv[i+1]*(i+1)=frac{1}{i!}=inv[i]$
所以我们可以求出$n!$的逆元，然后逆推，就可以求出$1...n!$所有的逆元了。
递推式为
$inv[i+1]*(i+1)=inv[i]$
所以我们可以求出 $displaystyle forall i, i!,frac{1}{i!}$ 的取值了。
然后这个也可以导出 $displaystyle frac{1}{i} pmod p$ 的取值，也就是
$displaystyle frac{1}{i!} imes(i-1)!=frac{1}{i} pmod p$
如果我们需要求 $0!$ 到 $n!$ 的逆元，对于每个元素都求一遍，就显得有点慢。
逆元可以看作是求倒数。那么不就有
$displaystyle frac{1}{(n+1)!} imes(n+1)=frac{1}{n!} pmod p$
int inv( int b, int p ) { int a, k; exPower( b, p, a, k ); if( a < 0 ) a += p; return a; } void init( int n ) { Fact[ 0 ] = 1; for( int i = 1; i <= n; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % Mod; INV[ n ] = inv( Fact[ n ], Mod ); for( int i = n - 1; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % Mod; return; }
三、不存在逆元
当$gcd(a,p)!=1$时，$a^{-1}equiv 0mod p$
当数和模数不互质时，不存在逆元，做题时要特判没有逆元的情况。