算法学习笔记(2): 逆元及其应用 - jeefies

逆元素，是指一个可以取消另一给定元素运算的元素

具体来说，对于实际的一些应用，如：

当我们想要求(11 / 3) % 10时

明显可以看出，是没有办法直接算的，这时就需要引入逆元

a 在模p意义下的逆元记作 a−1，也可以用inv(a)表示

则此时，(11 / 3) % 10就可以写成(11 * inv(3)) % 10

可以求出，inv(3)在模10意义下= 7

故(11 / 3) % 10 = (11 * 7) % 10 = ((11 % 10) * (7 % 10)) = (1 * 7) % 10 = 7

为什么我要多此一举在第三步再变换一次？

在实际应用中，a * b可能会很大以至于溢出，导致错误，所以分开来乘以减小数据规模

---

费马小定理

依据费马小定理(需要注意先决条件，a与p互质且p是质数)

费马小定理可以通过欧拉定理求解，详见后文欧拉定理

故此时可以有

扩展欧几里得算法

如果不满足先决条件呢？

这是相对来说的通发，但是总会有数据可以卡

令i=a−1换成等式可以知道

由于已知a,p，则此时可以通过扩展欧几里得算法求解 i 的值

扩展欧几里得算法可以参考这篇文章：扩展欧几里得算法。

是我认为写的非常好的一篇文章。

---

再推广一下？若 p 不为质数呢？

那么就要有欧拉定理来了

φ(p)指 [1,p] 中与p互质的数的个数。特别的，1也算。

举个例子：

• φ(7)=6 ，因为7是质数（所以在p为质数的时候就退化成费马小定理了）

• φ(6)=2，因为只有1, 5和它互质

但是如何求φ(p)呢？

1. 将p分解质因数，于是有 p=a1c1a2c2a3c3…ancn

2. 此时φ(p)=p∏i=1nai−1ai

---

欧拉定理证明

令集合A为 [1,p] 中所有与p互质的数，即

将A中每一个元素在模p意义下乘k，由于A中元素与p互质，且k也与p互质，可知

也满足为 [1,p] 中所有与p互质的数，故可知 A1=A2

左右相减，变形即可知 kφ(p)≡1(modp)

扩展欧拉定理

想必证明很简单，这里就不展开叙述了

---

补充：快速幂

可以看出，如果要利用欧拉定理，需要求ak，当k非常大的时候，就需要快速幂的帮助了

推荐阅读：快速幂

这里给出一种参考代码

// (a**x) % p
int quickPow(int a, int x, int p) {
    int r = 1;
    while (x) {
        // no need to use quickMul when p*p can be smaller than int64.max !!!
        if (x & 1) r = (r * a) % p;
        a = (a * a) % p, x >>= 1;
    }
    return r;
}

至于其中的那一行注释，主要是考虑到当a, p都很大（如：a = 1e15, p = 1e17 + 1时，a * a一定会溢出，所以需要“快速”乘来辅助）

实际上“快速”乘特别慢，是O(logn)的复杂度……所以叫龟速乘也不为过

推荐阅读：快速乘总结 - 一只不咕鸟，里面有更详细的阐述

这里给出快速乘的一种参考代码

// a*b % p O(log b)
int quickMul(int a, int b, int p) {
    // let b < a, to reduce a little time to process.
    if (a < b) std::swap(a, b);

    int r = 0;
    while (b) {
        if (b & 1) r = (r + a) % p;
        a = (a<<1) % p, b >>= 1;
    }
    return r;
}

---

notice: 适当的使用long long

线性求逆元

不妨设我们需要求i在模p意义下的逆元

很容易知道，1的逆元为1，所以边界条件就有了

令 p=ki+r, 放在模 p 意义下则有 ki+r≡0(modp)

两边同时乘以 i−1r−1 可以得到 kr−1+i−1≡0(modp)

所以，有了递推式

inv[i] = (p - p/i) * inv[p % i] % p;

线性求阶乘逆元

这个东西一般用于求组合数

我们先预处理出阶乘

fac[0] = 1;
for (int i = 1; i <= n; ++i)
    fac[i] = (fac[i - 1] * i) % p;

根据逆元定义i1i≡1(modp)

所以 inv(i!)≡1i!(modp)

稍微变换一下

所以有了递推式

ifac[i] = ifac[i + 1] * (i + 1) % p

我们逆着推，假设最大需要到n

ifac[n] = quickPow(fac[n], p - 2);
for (int i = n; i; i--)
    ifac[i - 1] = ifac[i] * i % p;

同时求逆元与阶乘逆元

还是逆元的本质是求倒数

稍微变换一下

inv[i] = ifac[i] * fac[i - 1] % p

合起来就是

for (int i = n; i; i--) {
    inv[i] = ifac[i] * fac[i - 1] % p;
    ifac[i - 1] = ifac[i] * i % p;
}

就可以在较少的常数下同时求得两者了