逆元

定义

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

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

当我们想要求(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) 的值

扩展欧几里得算法可以参考这篇文章：算法学习笔记(1): 欧几里得算法及其扩展

欧拉定理

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

那么就要有欧拉定理来了

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

(varphi(p) = ord(_p))

或者说, (varphi(p)) 的大小就是模 (p) 的一个完全剩余系的大小

而完全剩余系满足运算封闭，所以下文中 (A_1 = A_2) 也可换一种解释方法了

举个例子：

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

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

但是如何求(varphi(p))呢？

1. 将(p)分解质因数，于是有 (p = a_1^{c_1} , a_2^{c_2} , a_3 ^{c_3} ldots a_n^{c_n})

2. 此时(varphi(p) = p prodlimits_{i=1}^{n}frac {a_i -1}{a_i})

另外 (varphi(x)) 为积性函数

(gcd(x, y) = 1 implies varphi(xy) = varphi(x)varphi(y))

欧拉定理证明

数论证明

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

任取一个与 (p) 互质的数 (k)

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

也满足为 ([1, p]) 中所有与p互质的数，故可知 (A_1 = A_2)

补充，为什么两者相等：

我们考虑在 (A_2) 中取出 (ka_1) 与 (ka_2)，并假设两者同余。即 (ka_1 equiv ka_2 pmod p)

也就是 (p mid k(a_1 - a_2))

由于 (k) 与 (p) 互质，可以得到 (p | (a_1 - a_2))

同时，由于 (a_1, a_2) 在数列 (A_1) 中，意味着 (|a_1 - a_2| lt p)

由于有且仅有一个实数 (0) 满足绝对值小于 (p) 且能被 (p) 整除

所以可以知道 (ka_1 = ka_2)

也就是说，(A_2) 中不存在相同的两个元素。同时，(A_2) 是由 (A_1) 中所有元素变化而来，也就是说 (A_2) 是与 (A_1) 等价的剩余系

经过重排序之后，两者相等

这里也可以看出,为什么 (k) 需要与 (p) 互质

于是

即是

左右相减，变形即可知 (k^{varphi(p)} equiv 1 pmod p)

扩展-群论证明

2023/01/15 更新

考虑 (k) 与 (p) 互质, 意味着 (k) 在模 (p) 的完全剩余系中

我们将之看成一个群, 并且可以知道, 模 (p) 的完全剩余系为一个循环群

那么(exists t, k^t equiv 1 pmod p), 此时, (|<k>| |t) （(t) 是 (k) 的生成子群的大小的倍数）

根据某些定理：对于 (k in H, |<k>| mid |H|)

这个LaTeX格式太难看了QwQ。定理：循环群的大小一定是其生成子群大小的倍数

由于上文提及过 (varphi(p) = |H|)

也就是说，(exists s, st = varphi(p))

那么可以推出 (k^t equiv k^{varphi(p)} equiv1 pmod p)

这里也可以体现为什么 (k) 必须与 (p) 互质

只有 (k) 在 (_p) 中才能进行上述推论

扩展欧拉定理

没有互质的限制了

想必证明很简单，这里就不展开叙述了 其实是太复杂了，懒得写 QwQ

【模板】扩展欧拉定理 - 洛谷

补充：快速幂

可以看出，如果要利用欧拉定理，需要求(a^k)，当(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 = k i + r), 放在模 (p) 意义下则有 (ki + r equiv 0 pmod p)

两边同时乘以 (i^{-1}r^{-1}) 可以得到 (kr^{-1} + i^{-1} equiv 0 pmod p)

变换一下

所以，有了递推式

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;

根据逆元定义(i frac 1i equiv 1 pmod p)

所以 (inv(i!) equiv frac 1 {i!} pmod p)

稍微变换一下

所以有了递推式

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;
}

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

注意：如果模数小于要求的数的范围，那么……自求多福 QwQ