三种求逆元方法小结

标签：fine inv times 逆元 三种 jc 小结 mod

逆元（自学内容）

define：若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时，a关于模f的乘法逆元有解。
如果不互素，通过公式‘a/b mod p = (a mod (b·p)）/b’来转化
计算逆元方式：（条件a,p互质）

1. 费马小定理（ a\(^{p-1}\)≡1(mod p)）（a,p互质时，\(a^{fine(p)} = 1 (mod p))\)
   变形为a * a\(^{p-2}\)≡1(mod p)
   因为逆元x定义为a*x≡1(mod p),
   所以x=a\(^{p-2}\) (mod p)(可用快速幂求）

证明费马小定理：数学归纳法
\((x + 1)^p = x^p + 1\) (mod p)
证明2：a^fine(p)
{x1,x2,x3……\(x_{fine(p)}\)} <=> {ax1,ax2,……\(a*x_{fine(P)}\)}
两边集合乘起来：
\(Πx ≡ Πx* a^{fine(p)}\) (mod p)
\(0 ≡ Πx*（a^{fine(p)} - 1）\)
∵Πx 与 p互质，∴\(（a^{fine(p)} - 1）\)是p的倍数
∴$ a^{fine(p)} ≡ 1$ （mod p)

2. 拓展欧几里得算法（exgcd）
   用于求解模数p不是质数时的逆元。
   \(ax≡1 (mod\ p)\) 可变形为 \(ax - kp = 1\)
   然后就可以用exgcd来求了。复杂度 \(O(logn)\)

3. 阶乘逆元
   线性递推求阶乘：\(jc_i = jc_{i-1} \times i\ \%\ mod\)
   用费马小定理求 \(n!\) 的逆元 \(inv_n = qpow(n, mod-2)\)
   那么

\[jc_n \times inv_n \% mod = 1\\ jc_{n-1} \times n \times inv_{n} \% mod = 1 \\ ∴ inv_{n - 1} = inv_{n} \times n \\ \]

于是就可以递推求阶乘逆元，\(O(n)\) 预处理，\(O(1)\) 询问。

标签：fine,inv,times,逆元,三种,jc,小结,mod
From： https://www.cnblogs.com/water-flower/p/18568502