算法竞赛进阶数论核心定理与算法解析
同余理论与剩余系
在数论中，同余是研究整数除法余数性质的核心工具。若存在整数 \(n_1, n_2, m\)（其中 \(m > 0\)），使得 \(n_1\) 和 \(n_2\) 除以 \(m\) 的余数相同，即 \(n_1 = mq_1 + r\) 且 \(n_2 = mq_2 + r\)，则称 \(n_1\) 与 \(n_2\) 对模 \(m\) 同余，记作 \(n_1 \equiv n_2 \pmod m\)。
基于同余关系，可以将整数集划分为若干个等价类。所有模 \(m\) 同余于 \(r\) 的整数构成的集合称为模 \(m\) 的一个剩余类，记为 \(C_r\)。若从模 \(m\) 的 \(m\) 个不同剩余类中各选取一个代表元，这 \(m\) 个整数构成的集合称为模 \(m\) 的完全剩余系。
进一步地，若在完全剩余系中仅保留与 \(m\) 互质的元素，所构成的集合称为模 \(m\) 的简化剩余系（或缩系）。根据欧拉函数的定义，简化剩余系的元素个数严格等于 \(\varphi(m)\)。
欧几里得算法与裴蜀定理
最大公约数与辗转相除法
欧几里得算法（辗转相除法）基于以下恒等式计算最大公约数：
证明：设 \(a = qb + r\)，其中 \(r = a \bmod b\)。若 \(d = \gcd(b, r)\)，则 \(d \mid b\) 且 \(d \mid r\)。由于 \(a = qb + r\)，必然有 \(d \mid a\)，因此 \(d\) 是 \(a\) 和 \(b\) 的公约数，即 \(d \mid \gcd(a, b)\)。反之，若 \(k = \gcd(a, b)\)，则 \(k \mid a\) 且 \(k \mid b\)，从而 \(k \mid (a - qb) = r\)，即 \(k \mid \gcd(b, r)\)。两者互相整除，故 \(\gcd(a, b) = \gcd(b, a \bmod b)\)。
裴蜀定理 (Bézout's Identity)
对于不全为零的整数 \(a, b\) 和任意整数 \(m\)，线性丢番图方程 \(ax + by = m\) 存在整数解 \((x, y)\) 的充要条件是 \(\gcd(a, b) \mid m\)。若存在一组解，则必然存在无穷多组解。
证明与构造：必要性由整除的线性性质易得。充分性可通过扩展欧几里得算法构造证明。我们只需证明 \(ax + by = \gcd(a, b)\) 有解。在辗转相除的最后一步，有 \(\gcd(u, v) = \gcd(v, 1) = 1\)，此时显然有 \(0 \cdot v + 1 \cdot 1 = 1\)。通过逆向回代，假设已知 \(u x_0 + v y_0 = 1\)，且上一级状态为 \(\gcd(\lambda v + u, v)\)，则可构造新解 \(x_1 = y_0\)，\(y_1 = x_0 - \lambda y_0\)，逐层回推即可得到原方程的解。
利用数学归纳法，裴蜀定理可自然推广至 \(n\) 个变量：方程 \(\sum_{i=1}^n a_i x_i = m\) 有整数解当且仅当 \(\gcd(a_1, a_2, \dots, a_n) \mid m\)。
以下是扩展欧几里得算法的标准实现，用于求解 \(ux + vy = \gcd(u, v)\)：
long long extended_gcd(long long u, long long v, long long &coeff_u, long long &coeff_v) {
if (v == 0) {
coeff_u = 1;
coeff_v = 0;
return u;
}
long long gcd_val = extended_gcd(v, u % v, coeff_v, coeff_u);
coeff_v -= (u / v) * coeff_u;
return gcd_val;
}
欧拉定理与费马小定理
欧拉定理
若 \(\gcd(a, m) = 1\)，则 \(a^{\varphi(m)} \equiv 1 \pmod m\)。
证明：设模 \(m\) 的一个简化剩余系为 \(r_1, r_2, \dots, r_{\varphi(m)}\)。由于 \(\gcd(a, m) = 1\)，集合 \(\{a r_1, a r_2, \dots, a r_{\varphi(m)}\}\) 在模 \(m\) 意义下两两不同余，且均与 \(m\) 互质，因此它也是模 \(m\) 的一个简化剩余系。将两个集合的元素分别相乘，得到：
由于 \(\prod r_i\) 与 \(m\) 互质，两边约去该乘积即得 \(a^{\varphi(m)} \equiv 1 \pmod m\)。
费马小定理
当模数 \(m\) 为素数 \(p\) 时，\(\varphi(p) = p - 1\)，欧拉定理退化为费马小定理：若 \(p\) 为素数且 \(\gcd(a, p) = 1\)，则 \(a^{p-1} \equiv 1 \pmod p\)，等价于 \(a^p \equiv a \pmod p\)。
扩展欧拉定理
在算法竞赛中，处理大指数模运算时，常使用扩展欧拉定理进行降幂：
证明思路：对 \(m\) 进行质因数分解 \(m = p_1^{\alpha_1} \dots p_k^{\alpha_k}\)，只需对每个 \(p^\alpha\) 证明成立，再利用中国剩余定理合并。对于 \(\gcd(a, p^\alpha) \neq 1\) 的情况，必有 \(p \mid a\)。当 \(b \ge \varphi(m)\) 时，指数 \(b\) 足够大，使得 \(a^b\) 中包含的 \(p\) 的幂次大于等于 \(\alpha\)，此时 \(a^b \equiv 0 \pmod{p^\alpha}\)，而 \(a^{b \bmod \varphi(m) + \varphi(m)}\) 同样满足该条件，故两者同余。
乘法逆元
在模 \(m\) 意义下，若存在整数 \(b\) 使得 \(a \cdot b \equiv 1 \pmod m\)，则称 \(b\) 为 \(a\) 的乘法逆元，记作 \(a^{-1} \pmod m\)。逆元存在的充要条件是 \(\gcd(a, m) = 1\)。
求解方法
- 扩展欧几里得算法：求解方程 \(ax + my = 1\)，得到的 \(x\) 即为逆元。
- 欧拉定理/快速幂：由 \(a^{\varphi(m)} \equiv 1 \pmod m\)，可得 \(a^{-1} \equiv a^{\varphi(m)-1} \pmod m\)。当 \(m\) 为素数时，退化为 \(a^{p-2} \pmod p\)。
- 线性递推：用于求解 \(1\) 到 \(n\) 所有整数的逆元。时间复杂度 \(O(n)\)。
std::vector<long long> compute_inverses(int max_val, long long mod) {
std::vector<long long> inv(max_val + 1, 0);
inv[1] = 1;
for (int i = 2; i <= max_val; ++i) {
inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
}
return inv;
}
前缀积法求任意序列逆元
若需计算任意 \(n\) 个数 \(a_1, a_2, \dots, a_n\) 的逆元，可先计算前缀积 \(s_i = \prod_{j=1}^i a_j\)。利用上述方法求出 \(s_n^{-1}\) 后，倒序遍历计算 \(s_{i-1}^{-1} = s_i^{-1} \cdot a_i\)，最后正序遍历得到 \(a_i^{-1} = s_i^{-1} \cdot s_{i-1}\)。该方法仅需一次求逆操作，时间复杂度为严格的 \(O(n)\)。
中国剩余定理 (CRT) 与扩展 (EXCRT)
中国剩余定理
对于同余方程组 \(x \equiv a_i \pmod{m_i}\)，若模数 \(m_1, m_2, \dots, m_n\) 两两互质，令 \(M = \prod m_i\)，\(M_i = M / m_i\)，并求出 \(M_i\) 模 \(m_i\) 的逆元 \(M_i^{-1}\)，则方程组在模 \(M\) 意义下的唯一解为：
扩展中国剩余定理 (EXCRT)
当模数不满足两两互质条件时，需使用 EXCRT。核心思想是逐个合并方程。考虑合并两个方程：
将其转化为不定方程 \(\lambda m - \mu n = b - a\)。利用扩展欧几里得算法判断是否有解（需满足 \(\gcd(m, n) \mid (b - a)\)），并求出一组特解 \(\lambda_0\)。合并后的新方程为：
通过不断两两合并，最终可将整个方程组化简为单一同余方程。
威尔逊定理 (Wilson's Theorem)
对于任意素数 \(p\)，满足 \((p-1)! \equiv -1 \pmod p\)。
证明：在集合 \(\{1, 2, \dots, p-1\}\) 中，每个元素均与 \(p\) 互质，故都存在唯一的乘法逆元。解方程 \(x^2 \equiv 1 \pmod p\)，在 \(1 \le x \le p-1\) 范围内仅有 \(x = 1\) 和 \(x = p-1\) 两个解，即只有 \(1\) 和 \(p-1\) 的逆元是自身。其余元素均可与其逆元两两配对，乘积模 \(p\) 为 \(1\)。因此，\((p-1)! \equiv 1 \times (p-1) \times 1^{\frac{p-3}{2}} \equiv p-1 \equiv -1 \pmod p\)。
卢卡斯定理 (Lucas' Theorem)
对于素数 \(p\) 和非负整数 \(n, m\)，组合数模 \(p\) 满足以下递推关系：
直观解释：将 \(n\) 和 \(m\) 表示为 \(p\) 进制数，\(\binom{n}{m} \bmod p\) 的值等于 \(n\) 和 \(m\) 在 \(p\) 进制下对应数位上的组合数模 \(p\) 的乘积。该定理极大地优化了大组合数对小素数取模的计算效率。
