乘法逆元一
导入：分数取模
考虑一个式子 \(x \equiv \dfrac{1}{2}\ (mod\ 7)\) ，即求一个数 \(x\) ，它与 \(\dfrac{1}{2}\) 模 7 的结果相同，称为 \(x\) 与 \(\dfrac{1}{2}\) 对模 7 同余。
分数取模不同于整数取模，但我们仍可以利用模运算的性质解决此题。
模运算时两边同乘相同的数， 两边仍然同余。
所以将两边同乘 2，原式即化简为 \(2x\equiv 1\ (mod\ 7)\) ，即求解方程组 \(2x-7y = 1\) 。
因为 \(gcd(2,7)=1\)，所以接下来使用扩展欧几里得算法就可以解决。
简述：乘法逆元的定义
如果在一个群 \(G\) 中，对于一个数 \(b\) ， 存在乘法逆元且为 \(x\) ， 那么就有 \(bx=xb=e\) ，其中 \(e\) 为群 \(G\) 的单位元。
对于单位元 \(e\) 我们有 \(eb=be=b\)
定义太多不看版：
就是说如果 \(x\) 是数 \(b\) 的乘法逆元，那么 \(a*b*x=a\)
考虑有理数域(理解为全体有理数构成的集合，所有选择的数都是里面的)，对于一个数 \(b\) ，它的逆元就是 \(\dfrac{1}{b}\) (注意这里不是模运算意义下的逆元)，而这里的单位元就是数字 1.
主线：模运算意义下的乘法逆元
首先，我们假设模数为一个质数，记为 \(p\) 。(模数为质数这个条件非常重要，在求解乘法逆元时我们会看到)
然后，接下来的讨论，我们都是在模意义下。(注意，之后的单个字母，表示的都是整数)
那么，我们定义一个数 \(b\) 的乘法逆元为\(x\) ，当且仅当 \(bx\equiv1\ (mod\ p)\)
为什么会这么定义呢？
显然，我们有 \(a*b*x\equiv a\ (mod\ p)\) ，这不就是乘法逆元的定义吗，只不过是在模运算下的。
这样有什么用呢？
考虑式 \(x\equiv \dfrac{1}{b}\ (mod\ p)\)
两边同乘 \(a\) ，得到 \(ax\equiv \dfrac{a}{b}\ (mod\ p)\)
…对比一下分数取模中的式子，是不是感觉有点熟悉…
最简单的，我们发现了，数 \(b\) 的乘法逆元 \(x\) ，在模意义下，同余于 \(\dfrac{1}{b}\) ，即前文的 \(x\equiv \dfrac{1}{b} \ (mod\ p)\)
进一步，我们发现，这样就可以清楚地定义分数取模的解决方法了。
对于式子 \(c\equiv \dfrac{a}{b}\ (mod\ p)\) ，我们只需要计算 \(b\) 的乘法逆元 \(x\) ，那么原式就可以化简为 \(c\equiv ax\ (mod\ p)\)
前行：关于乘法逆元的求解
如果模数 \(p\) 为质数
首先，根据费马小定理，我们有 \(b^{p-1}\equiv 1\ (mod\ p)\)
…显然，数 \(b\) 的逆元即为 \(b^{p-2}\)
如果 \(p\) 不为质数呢
费马小定理只适用于 \(p\) 为质数的情况，但是，我们有更通用的算法，欧拉定理。
如果 \(p\) 与 \(b\) 互质，那么我们就可以使用欧拉定理来求解。
欧拉定理的表示如下 \(b^{\varphi(p)-1}\equiv1\ (mod\ p)\)
其中 \(\varphi(x)\) 定义为 1 到 \(x\) 之间与 \(x\) 互质的数的个数。
当然，也可以使用扩展欧几里得算法。
那么，如果 \(p\) 与 \(b\) 不互质呢？
往下看。
深入：关于模意义下乘法逆元更深层的一些讨论
1. 模逆元的存在性:当 \(p\) 与 \(b\) 不互质时，模意义下的乘法逆元，不存在
我们回顾一下乘法逆元的定义：我们定义一个数 \(b\) 的乘法逆元为\(x\) ，当且仅当 \(bx\equiv1\ (mod\ p)\)
我们改写一下这个式子: \((kr)*x -1=cr\) ，其中 \(r=gcd(p,b)\neq 1\) ， \(kr=b\) ， \(cr=q*p\) ( \(p\) 的某个倍数)
..好了，已经可以发现 \(kr*x\) 和 \(cr\) 都为 \(r\) 的倍数，但是因为 \(r\neq1\) ，所以 \(1\) 不为 \(r\) 的倍数。
这说明等式不成立，即乘法逆元不存在。
2.模逆元 \(x\) 一定为整数吗
首先，模逆元定义为 \(x\) 整数。
其次，定义为分数并没有解决问题，比如我有 \(b*\dfrac{1}{b}\equiv1\ (mod\ p)\) …
可以知道的是，模运算对于加减乘三种运算具有很好的性质，但是对于除法却不是很好，所以我们是要将除法化为乘法。
3.在OI中的应用
我们知道，在OI中，通常数据是有限制的，此时出题人一般会给你一个模数 \(p\)
比如计数类问题，还有分数需要保持精度的问题。
而模运算将除法变成乘法后，就可以有效利用乘法在模运算中的性质，举例：
我们要计算 \(\dfrac{a}{b}\ mod\ p\) ，就可以化为 \(((a\ mod\ p)*(x\ mod\ p))\ mod\ p\) ，其中 \(x\) 为 \(a\) 的逆元。
这样就可以大幅度降低数据大小，同时保证除法的精度。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233109.html原文链接：https://javaforall.net
