四种方法乘法逆元！四种！
共 2042字，需浏览 5分钟
·
2021-12-23 01:54
写在前面
刷题过程中，为了避免高精度的整数运算，常常会要求答案对某个数取模。但这衍生了一个新问题，如果运算过程中涉及了除法，如，如果先对a和b取模再做除法，会导致答案错误。比如:
但是，
为了解决这个问题，我们需要学习新知识：模运算下的乘法逆元。
下文中会用到一些欧几里得算法的知识，忘了的老铁可以点这里：浅谈辗转相除法
乘法逆元
什么是逆元呢？百度百科告诉我们：逆元是指一个可以「取消」另一给定元素运算的元素。
比如，在实数的加法中，任意实数 a 和它的相反数 -a，互为加法逆元。因为对于任意实数 x，加上a之后，再加上-a，仍然等于 x，换言之，-a「取消」了x和a的加法运算。
再比如，在实数的乘法中，任意不为0的实数b和它的倒数，互为乘法逆元。因为对于任意实数x，乘上b之后，在乘上，仍然等于x，换言之，「取消」了x 和 b 的乘法运算。
接下来看看模运算下的乘法逆元定义：如果两个整数a 和 b 满足 ，即 ，则称，a 和 b 互为模 p 的乘法逆元。
换言之，如果整数a, b, p 满足，那么 b 可以「取消」 a 和任意整数x在模p时的乘法，即 a 和 b 互为模 p 的乘法逆元。即 ，证明过程如下：
举个实际的例子：比如 10 和 12 互为模7时的乘法逆元。然后再找个整数，比如 18，此时有：
另有，
何时存在乘法逆元
结论
先说结论：「a 与 p 互质」 是 「存在a关于模p的乘法逆元b」 的充分必要条件。
存在逆元 → 互质
证明 「a 与 p 互质」 是 「存在乘法逆元b」 的必要条件。不妨先假设 a 与 b 互为模p时的乘法逆元，且a与p的最大公约数为d，则有：
显然，a*b-1 为 p 的 n 倍，n 为整数，则上式转化为：
将等式中的a与p用d代替，则等式转化为：
显然，x*b-n*y是一个整数，所以仅当d为1时，即a与p互质时，上述等式才可能成立。
互质 → 存在逆元
证明 「a 与 p 互质」 是 「存在乘法逆元b」 的充分条件。
在证明之前先来回忆一下辗转相除法：
不妨用r来表示模运算的结果：
将上式用除法表示，则有：
由上述的m+2个等式移项可得：
将 rm-1，rm-2 ... 以及 r1 依次代入
可以得到用 a，p 以及 ni表示的等式：
其中，x 与 y 为 n1，n2，n3 ... 的加减乘的运算结果，显然为整数。
得证，当 a 与 p 互质时，存在整数x与y 满足
即，当 a 与 p 互质时，存在整数x 与 a互为模p时的乘法逆元。
如何计算乘法逆元
扩展欧几里得算法
回忆一下欧几里得的递归过程：
当 a 与 b 互质时，有 x，y，x'，y' 满足：
将上式合并移项：
令x，y，x'，y' 满足下述关系，则对于任意 a 和 b 上述公式都能成立。
😯好巧，这就是我们要寻找的x，y和x'，y'的计算公式。另外，当 b = 0，即到达欧几里得算法的递归边界时，令 x = 1, y = 0 即可满足ax+by=1(此时的a显然为1)。
于是我们得到了下述代码，最终得到的 x 即为 a 在模 b 时的乘法逆元，当然前提是函数的返回值为1，即 a 与 b 互质。
int exgcd(int a,int b,int &x,int &y)
{
if(b==0) {
x=1;y=0;
return a;
}
int r = exgcd(b,a%b,x,y);
int t = y;
y = x-(a/b)*y;
x = t;
return r;
}
费马小定理 & 快速幂
费马小定理：若 p 为素数，且 gcd(a, p) = 1，则满足
于是，a 在模 p 时的乘法逆元为，可用快速幂求得。
inline int quick_power(int a, int b, int p) {
int ans = 1;
a = (a % p + p) % p;
for (; b; b >>= 1) {
if (b & 1) ans = (a * ans) % p;
a = (a * a) % p;
}
return ans;
}
// quick_power(a, p-2, p) 即为 a 的乘法逆元。
值得注意的是，该算法仅在 p 为素数时有效，而扩欧并没有该限制。
线性求1到n中每个数的逆元
现在要求1到n中每个数i在模p时的乘法逆元。
特别的，i = 1时，其乘法逆元i-1为1。
当 i > 1 时，不妨先设：
则有：
而且，在递推过程中，当我们要求时，对于任意的都是已知的啦(因为 p mod i肯定小于 i)，所以可根据 通过常数次运算得到。
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p-p/i)*inv[p%i]%p;
}
求任意n个整数的乘法逆元
设有 n 个整数，分别为 a1，a2，a3...，对应的逆元为a1-1，a2-1，a3-1...。
设Si 为 a1 到 ai i 个数的乘积，Si-1 为 a1-1 到 ai-1 i 个数的乘积。那么 Si 与 Si-1 互为逆元。证明过程如下：
接下来，我们可以先求出 S1 到 Sn，然后通过扩展欧几里得或者快速幂求出 Sn 的乘法逆元 Sn-1。
又有
换言之，我们可以利用 ai可以取消ai-1乘法运算的性质，由Si-1 计算出 Si-1-1。
这样就可以O(n)的计算出所有的 Si-1。
最后，由Si-1以及Si 计算出所有的 ai-1：
s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = quick_power(s[n], p - 2);
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;