乘法逆元 学习笔记
问题
用来解决模域下的除法问题。
求解
乘法逆元的定义：\(ab\equiv 1 \pmod p\)，则\(b\)称为\(a\)在模\(p\)域下的乘法逆元。乘法逆元不一定存在，存在条件请参见下文。
这样我们就可以轻松解决模域下的除法问题。即假设我们要求\(\frac{a}{b} \bmod p\)的值，用\(inv(x)\)表示\(x\)在模\(p\)域下的乘法逆元，则\(\frac{a}{b} \bmod p=\frac{a\cdot b\cdot inv(b)}{b}\bmod p=a\cdot inv(b) \bmod p\)，所以我们把除法变成了乘法，就可以利用乘法在模域下的一些性质对原问题进行求解或转化。
问题在于如何求出\(inv(b)\)。求乘法逆元有许多方法。
扩展欧几里得
根据乘法逆元的定义，我们要求\(inv(a)\)，就是求同余方程\(ax\equiv 1 \pmod p\)的最小整数解。
考虑将该同余方程转化为一般形式，即\(ax+py=1\)。
很容易就能求出\(x\)的最小整数解。
根据裴蜀定理可知，方程\(ax+by=c\)只有当\(gcd(a,b)|c\)时才有整数解。所以只有当\(gcd(a,p)=1\)时，逆元才唯一存在。
费马小定理
费马小定理：当\(p\)是质数时，\(a^{p-1}\equiv 1 \pmod p\)。即\(a\cdot a^{p-2}\equiv 1\pmod p\)。所以\(inv(a)=a^{p-2}\)。
欧拉定理
欧拉定理：当\(a,p\)互质时，\(a^{\varphi(p)}\equiv 1 \pmod p\)。即\(a\cdot a^{\varphi(p)-1}\equiv 1\pmod p\)。所以\(inv(a)=a^{\varphi(p)-1}\)。
\(\varphi(p)\)即欧拉函数，表示小于等于\(p\)的正整数中，与\(p\)互质的数的个数。
因为当\(p\)是质数时，\(\varphi(p)=p-1\)，所以费马小定理是欧拉定理的特殊形式。
\(\varphi(p)\)的求法不详细介绍。
特例
还有一些奇怪的特例，例如求\(1\)到\(n\)所有数在模\(p\)域下的逆元，还有\(1\)到\(n\)所有数的阶乘在模\(p\)域下的逆元，这些可以\(O(n)\)求出。
不详细介绍。
