同余

同余ψ(｀∇´)ψ

几个定义：

同余：若 \(a \bmod m = b \bmod m\)，称 \(a\) 与 \(b\) 在模 \(m\) 意义下同余，记为 \(a \equiv b \pmod m\)。
同余类：对于 \(\forall a \in [0, m), \{a + km\}(k \in \mathbb{Z})\) 构成一个模 \(m\) 余数相同的集合，记为 \(\overline{a}\)，称为模 \(m\) 的一个同余类。
剩余系：\(\overline{0}, \overline{1}, \dots \overline{m - 1}\) 构成 \(m\) 的完全剩余系
简化剩余系：所有 \(\gcd(a, m) = 1, a < m\) 的 \(\overline{a}\) 构成 \(m\) 的简化剩余系，这样的同余类有 \(\varphi(n)\) 个。
简化剩余系关于模 \(m\) 乘法封闭，这个性质非常重要，因为它可以用来证明两个简化剩余系是相等的，进而证明一些结论，这个结论的证明比较简单：考虑 \(\forall a, b, \gcd(a, m) = \gcd(b, m) = 1, a,b < m\)，因为 \(a, b\) 和 \(m\) 不含有相同质因子，所以 \(ab\) 和 \(m\) 也没有公共质因子。

扩展欧几里得ψ(｀∇´)ψ

Bézout 定理：\(\forall a, b\in \mathbb{Z}, \exists x, y \in \mathbb{Z}, ax + by = \gcd(a, b)\)。

证明：

欧几里得算法求 \(\gcd\) 的最后一步一定是 \(b = 0, a \not ={0}\)，此时显然存在这样的 \(x,y \to x = 1, y = 0)\)。

我们记上一层（已经计算出来的）的 \(x, y\) 为 \(x, y\)，这一层的 \(x, y\) 为 \(u, v\)，\(a, b\) 是当前层的。

那么假设上一层（\(\gcd(b, a\bmod b)\)）已经满足条件则有：\(bx + (a\bmod b)y = \gcd(a, b)\)。（就是当前层递归下去）

假设存在 \(u, v \in \mathbb{Z},au + bv = \gcd(a, b)\)，那么 \(au + bv = bx + (a\bmod b)y = \gcd(b, a\bmod b)\)。

令 \(a \bmod b = a - b\lfloor\dfrac{a}{b}\rfloor\)。

那么 \(au + bv = bx + (a - b\lfloor\dfrac{a}{b}\rfloor)y =ay + b(x - \lfloor\dfrac{a}{b}\rfloor y)\)。

可以发现 \(x - \lfloor\dfrac{a}{b}\rfloor y \in \mathbb{Z}\)。

所以 \(u = x, v = x - (a - b\lfloor\dfrac{a}{b}\rfloor)y\) 即可，归纳可以证明。

这里的思路是一个很经典的想法，考虑假设上一层存在答案，然后想办法利用上一层的答案把这一层的结果化成答案形式并归纳证明。

用稍微高级点的东西解释，就是说，\(\gcd(a, b)\) 是 \(a, b\) 的一个线性组合。

还有一个推论：一个整数为 \(a, b\) 的线性组合，当且仅当它能被 \(\gcd(a, b)\) 整除，也就是说，\(\gcd(a, b)\) 一定是 \(a,b\) 的线性组合当中最小的。

这个可以反证法，也可以直接考虑欧几里得算法的最后一步，我们最后得到的两个数是 \((x, 0)\) 的形式，这个 \(x\) 就是我们求的 \(\gcd\)，而考虑辗转相除的过程，这个“线性组合”的大小是不断缩小的，所以 \(\gcd\) 就是最小的线性组合。

然后这个东西就可以解这个方程的一个解 \((x, y)\)：\(ax + by = \gcd(a, b)\)。

实现：

int exgcd(int a, int b, int &x, int &y) {
    if(!b) { x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, x, y);
    int z = x; x = y; y = z - y * (a / b);
}

如果是要求 \(ax + by = c\) 的这种，我们先求一个 \(ax + by = \gcd(a, b)\) 的情况。

然后整体乘上 \(\dfrac{c}{\gcd(a, b)}\) 即可，这同时也说明这个方程有整数解的充要条件是 \(\gcd(a,b) | c\)。

不过这里求出来的是一组特解，我们不妨设为 \((x_0, y_0)\)，现在考虑求通解。

找通解的一个 Trick 就是从特解出发，设一组不是特解的解，尝试让这组解和特解有什么关系，然后就能写出通解的式子了。

记 \(d = \gcd(a, b)\)

设 \((x, y) \not=(x_0,y_0)\)，满足 \(ax + by = d\)。

所以 \(ax_0 + by_0 = ax + by \iff a(x_0 - x) = b(y - y_0)\) 且 \(x_0 - x, y - y_0 \not= 0\)。

所以 \(\dfrac{a}{b} = -\dfrac{y - y_0}{x - x_0}\)。可以看作所有解都是在一条斜率为 \(-\dfrac{a}{b}\) 的直线上的点。

这里是斜率式，不太方便，我们尝试改写成其他形式：

\(d \not= 0\)，那么有 \(\dfrac a d x + \dfrac b d y = 1\)，这是直线的截距式。

\(x_0 - x, y - y_0\) 以及直线构成的三角形和直线截出来的三角形相似。

不难写出：\(x = x_0 + t\dfrac b d, y = y_0 - t\dfrac a d,t \in\mathbb{Z}\)。

线性同余方程ψ(｀∇´)ψ

给定 \(a, b, m \in \mathbb{Z}\)，求 \(ax \equiv b \pmod m\) 的解。

因为 \(m | ax - b\)，令 \(-ym = ax - b\)，

所以 \(ax + my = b\)，所以有解肯定需要 \(\gcd(a, m)\ |\ b\)，这里就是上面提到的东西，乘上一个 \(\dfrac{b}{\gcd(a, m)}\) 即可。

解集显然是 \(\{y | y\equiv x \pmod{\dfrac{m}{\gcd(a, m)}}, y \in \mathbb{Z}\}\)，\(x\) 是特解。

欧拉定理ψ(｀∇´)ψ

若 \(\gcd(a, n) = 1\)，则 \(a^{\varphi(n)} \equiv 1 \pmod n\)。

看到这个 \(a^{\varphi(n)}\)，我们情不自禁地想到了简化剩余系。

首先有个结论是，如果 \(b \not ={c}\)，\(\overline{ab}\) 和 \(\overline{ac}\) 一定不是同一个同余类。

因为简化剩余系在模 \(n\) 意义下乘法封闭，且 \(\gcd(a, n) = 1\) 所以 \(\overline{aa_i}\) 也属于简化剩余系。

那么 \(\overline{aa_1}, \overline{aa_2}, \overline{aa_3}, \dots \overline{aa_{\varphi(n)}}\) 就等价于 \(\overline{a_1}, \overline{a_2}, \overline{a_3}, \dots \overline{a_{\varphi(n)}}\)。

那么 \(\prod a_i \equiv \prod(aa_i) \equiv a^{\varphi(n)}\prod a_i \pmod n\)。

由 \(\prod a_i \equiv a^{\varphi(n)}\prod a_i \pmod n\)，两边除掉，就得到了欧拉定理。

当然如果 \(n\) 是质数，\(\varphi(n) = n - 1\)，这个东西可以证明费马小定理。

然后这个东西还有一个推论，之后补，它可以用来给乘方运算取模。

费马小定理ψ(｀∇´)ψ

对于 \(a \in \mathbb{Z}\)，有一个质数 \(p\)，且 \(\gcd(a, p) = 1\)，则有 \(a^{p - 1} \equiv 1 \pmod p\)。
对于 \(a \in \mathbb{Z}\)，有一个质数 \(p\) 则有 \(a^{p} \equiv a \pmod p\)。

前者带入欧拉定理即可。

后者这里能去任意 \(p\) 的原因就是，我们假设前者成立，两边同时乘上一个 \(a\)，然后互质的情况显然对，如果 \(a\) 是 \(p\) 的倍数，显然余数为 \(0\) 也成立。

然后我们证了后者再倒回去就行了。

假设后者成立，根据二项式定理：

\((a + 1)^p = a^p + a^{p - 1}\dbinom{p}{1} + \dots a\dbinom{p}{p - 1} + 1\)

因为 \(p\) 是质数，所以 \(p\ |\ \dbinom{p}{k}, 1\le k < p\)，因为 \(p\) 不会被消掉。

那么它们在模 \(p\) 意义下就等于 \(0\)。

所以 \((a+1)^p \equiv a^p + 1 \pmod p\)。

将后者带入：\((a+1)^p \equiv a + 1 \pmod p\)。

然后就成立了。

乘法逆元ψ(｀∇´)ψ

乘法逆元的定义大概就是，如果 \(a \times inv \equiv 1 \pmod p\)，那么 \(inv\) 就是 \(a\) 在模 \(p\) 意义下的乘法逆元，一般记作 \(a^{-1}\) 或者 \(inv(a)\)。

用群论的写法就是，我们现在有一个模 \(p\) 意义下的乘法群，幺元为 \(1\)，乘法逆元就是 \(a\) 的在这个群里的逆元。

可以证明乘法逆元是唯一的，这个就直接反证法，消去即可。

一般在 OI 中我们只讨论模质数意义下的乘法逆元，因为其他情况下，并不是所有数都有乘法逆元。

你可以理解成 \(a\times a^{-1} \equiv a\times inv \equiv1 \pmod p\)，也就是说可以用来处理带取模的除法。

因为加减乘在取模意义下都是封闭的，但是除法就没法处理。

所以为了让除法在取模意义下也是封闭的，我们把除法转化成乘上分母的乘法逆元即可。

也就是说 \(\dfrac{a}{b} \equiv a\times b^{-1} \equiv a\times inv(b) \pmod p\)。

有一个小注意点是，\(inv(a)\times inv(b) = inv(ab)\)，这个从定义上的封闭性即可知道。

求法可以直接用费马小定理：

如果 \(a,p\) 互质，则 \(a\) 在模 \(p\) 意义下的逆元是 \(a^{p-2}\)，快速幂即可 \(O(\log n)\) 求，这里也说明了只有 \(p\) 是质数的时候，对于任意给定的值域小于 \(2p\) 的序列都可以求出逆元。

然后我们对于一个值域为 \([1,n]\) 的数列，我们要求出每一项在 \(\bmod\ p\) 意义下的逆元（\(p\) 是质数），这样复杂度是 \(O(n \log p)\) 的，我们不希望这么做，考虑一个可以线性递推的做法

首先令 \(r = i\bmod p\)，令 \(\lfloor p/i\rfloor = k\)，即 \(ki+r \equiv 0\pmod p\)。

然后就是移项，把 \(i\) 单独留一边，另外一边是一个小于 \(i\) 的数的逆元的形式。

\[ \begin{aligned} ki+r &\equiv 0 &\pmod p\\ i &\equiv \dfrac{-r}{k} &\pmod p\\ i &\equiv -r \times inv(k) &\pmod p\\ i &\equiv -inv(k)\times r &\pmod p\\ inv(i) &\equiv -k\times inv(r) &\pmod p\\ inv(i) &\equiv -\lfloor p/i\rfloor \times inv(p \bmod i) &\pmod p \end{aligned} \]

最后一步这里有负数，加一下（如果 \(x < 0\)，则 \(x \equiv p + x \pmod p\) ）：

\[ inv(i)\equiv (p - \lfloor p/i\rfloor) \times inv(p \bmod i) \pmod p \]

于是就能线性递推了，组合数啥的也能求：

Code

const int mod = 998244353;

int inv[si], fact[si], invf[si];
void init(int n) {
    inv[1] = 1, fact[0] = invf[0] = 1;
    for(int i = 2; i <= n; ++i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 1; i <= n; ++i)
        fact[i] = 1ll * fact[i - 1] * i % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
}
int C(int n, int m) {
    if(m < 0 || n < m) return 0;
    return 1ll * fact[n] * invf[n - m] % mod * invf[m] % mod;
}
int Catalan(int n) {
    return 1ll * C(n * 2, n) % mod * inv[n + 1] % mod;
}

中国剩余定理(CRT)ψ(｀∇´)ψ

给定 \(n\) 个两两互质的整数 \(m_i\)，求以下线性同余方程组的解：

\[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \cdots \\ x \equiv a_n \pmod{m_n} \end{cases} \]

CRT：设 \(m = \prod m_i,M_i=\dfrac{m}{m_i}\)，\(t_i\) 为线性同余方程组 \(M_it_i \equiv 1 \pmod{m_i}\) 的一个解，则方程组的解为：

\[ x = \sum\limits_{i = 1}^n a_iM_it_i \]

因为 \(m_i\) 两两互质，所以显然 \(M_i\) 是除了 \(m_i\) 以外的所有 \(m_j\) 的倍数。

所以 \(\forall k \not= i, a_iM_it_i \equiv 0 \pmod{m_k}\)。

然后 \(a_iM_it_i \equiv a_i \pmod{m_i}\)，这个是因为 \(t_i\) 是 \(M_i\) 关于 \(m_i\) 的乘法逆元，所以就有上面的式子了。

或者说，你可以考虑成，先只满足其中一个的要求，然后合并起来。

唯一解就模一个 \(m\) 就行。

这个东西是一定有唯一解的，感觉非常显然，但是我不会证明，可能和上面的构造过程有些关系。

#define int long long
int crt(std::vector<int> &r, std::vector<int> &m) {
    int n = 1, ans = 0;
    for(int i = 0; i < (int)m.size(); ++i) 
        n = n * m[i];
    for(int i = 0; i < (int)m.size(); ++i) {
        int mi = n / m[i], b, y;
        exgcd(mi, m[i], b, y); // 求逆元，因为 mi 与 m[i] 互质所以 gcd = 1, 可以得到 mi * b = 1 (mod m[i])
        ans = (ans + r[i] * mi * b % n) % n;
    }
    return (ans % n + n) % n;
}

EXCRTψ(｀∇´)ψ

用于模数两两不互质的情况。

考虑两个方程怎么做。

假设 \(x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod{m_2}\)。

按照类似 \(\gcd\) 那边的套路：

\(x = m_1p + a_1 = m_2q + a_2, p, q \in \mathbb{Z}\)。

然后可以知道 \(m_1p - m_2q = a_2 - a_1\)，然后这东西就是类似线性同余的东西。有解当且仅当 \(\gcd(m_1, m_2)\ |\ a_2 - a_1\)。

然后就 exgcd 解一下，显然这两个方程的解应该是 \(m_2q + a_2 \pmod{\operatorname{lcm}(m_1, m_2)}\)。

然后我们就直接合并多个方程就可以了。

最后更新: October 23, 2023