中国剩余定理（CRT）与 EXCRT 学习笔记

chlchl · 2022-06-09 21:56:04 · 算法·理论

前言

中国剩余定理，是中国古代的一个典型的数学问题。它用于解决 (同一个数)(模多个值)(出现多个不同余数) 的问题。典型代表是韩信点兵。

看到网上的博客模模糊糊的，本蒟蒻决定按照自己的理解梳理一下这俩玩意（毕竟它们实在是太重要了），同时也方便后来人学习。

本篇博客将分为两部分：传统的 CRT 和扩展 CRT。

Part 1：中国剩余定理（CRT）

假设有以下 n 个方程：

且对于任意一组 i,j(i,j\leq n) 有 i\neq j\ and\ m_i\bot m_j（互质），你要如何快速求出符合条件的最小非负整数 x 呢？

缩放问题

我们先讨论特殊情况：n=3 时的解法。就用古籍上记载的题吧：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

意思是：现在有一堆物品，3 个为一组剩 2 个，5 个为一组剩 3 个，7 个为一组剩 2 个。问这堆物品（最少）有几个？

答案是 23。怎么得出的呢（废话，肯定不是枚举）？

1. 求出三个数：lcm(3,5)=15,lcm(3,7)=21,lcm(5,7)=35。
2. 将 15\times 2,21\times 3,35\times 2，即分别乘上另外一个数除以该数的余数。
3. 相加，得 30+63+140=233。233 符合条件，但不是最小，模上 lcm(3,5,7)=105 得 23，所以答案即为 23。

看似很牛 X。实际上，这些步骤是有严格数学证明的。

下面，我们一步一步看（这是最关键的地方，其他博客就是这里讲得一塌糊涂）。

原理及推导过程

首先需要明确同余的两个性质：

1. 若 a\equiv b\pmod m，则 a+km\equiv b\pmod m（k 为任意非零整数）。
2. 若 a\equiv b\pmod m，则 ak\equiv bk\pmod m。

我们假设有三个未知数 p_1,p_2,p_3 满足 p_1\equiv 2\pmod 3,p_2\equiv 3\pmod 5,p_3\equiv 2\pmod 7。

现在，我们稍微合并一下三个方程：

• 若 p_1+p_2\equiv 2\pmod 3，则根据性质 1，3\mid p_2。
• 若 p_2+p_3\equiv 3\pmod 5，则根据性质 1，5\mid p_3。
• 若 p_3+p_1\equiv 2\pmod 7，则根据性质 1，7\mid p_1。

现在，我们考虑构造答案：p_1+p_2+p_3 必定是这三个方程的公共解，所以进行以下变形：

• 若 p_1+p_2+p_3\equiv 2\pmod 3，则根据性质 1，3\mid p_3。
• 若 p_1+p_2+p_3\equiv 3\pmod 5，则根据性质 1，5\mid p_1。
• 若 p_1+p_2+p_3\equiv 2\pmod 7，则根据性质 1，7\mid p_2。

整理一下，现在我们得到一些关于 p_1,p_2,p_3 的余数信息：

如果还是不懂，我转化一下，即：

所以，我们就要从 35,21,15 的倍数（条件一）中找到符合条件二的数。

这该咋找呢？我们想到了扩展欧几里得。

我们以求 p_1 为例。设 p_1=35k，利用扩欧求出 35k\equiv 1\pmod 3（转化为 35k+3y=1①）的解 k_0。

为什么不直接求出 35k+3y=2 的解呢？虽然在这个方程中没问题，但是在某些方程中，两个系数的最大公因数不一定能被 a_i 整除。这时，根据裴蜀定理，方程式无解的。况且根据性质 2，求出 k_0 后，乘上 a_1(=2) 即为 k。

所以，当我们求出方程①的解后，p_1=35\times k_0\times a_1。

剩下的 p_2,p_3 同理，只是把数换了，方法是不变的！

得到了 p_2,p_3 后，我们将它们相加，得到了一个完全符合条件的数（记为 x_0）。这个数必定是上面三个方程的解，但不一定是最小的。所以还是老套路：记 l=\text{lcm}(m_1,m_2,m_3)，则 x_0\leftarrow (x_0\bmod l+l)\bmod l。

为什么模上 lcm(m_1,m_2,m_3) 不会影响取模三个数的结果呢？

我们知道，模上一个数等于减去若干个这个数。而由性质 1 变形得 a-km\equiv b\pmod m（可以理解为 k 是负整数时，又变回了原式）。然后因为 l 同时是 m_1,m_2,m_3 的倍数，所以 x_0-lk\equiv a_i\pmod {m_i}。因为要求左边最小，即 k 最大，所以直接取模即可。

最后给一首诗帮助记忆：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。

至此，我们已经解决了三个方程的中国剩余定理。接下来，我们就扩展一下，看看 n 个数如何解决。

扩大问题

现在升级一波：有 n 个同余方程的方程组该如何求解？

设有 p_1,p_2,\cdots,p_n 满足方程。

现在，我们稍微合并一下 n 个方程：

• 若 p_1+p_2\equiv a_1\pmod {m_1}，则根据性质 1，m_1\mid p_2。
• 若 p_2+p_3\equiv a_2\pmod {m_2}，则根据性质 1，m_2\mid p_3。
• 若 p_3+p_4\equiv a_3\pmod {m_3}，则根据性质 1，m_3\mid p_4。
• \cdots
• 若 p_n+p_1\equiv a_n\pmod {m_n}，则根据性质 1，m_n\mid p_1。

再扩展成 3 个数：

• 若 p_1+p_2+p_3\equiv a_1\pmod {m_1}，则根据性质 1，m_1\mid p_3。
• 若 p_2+p_3+p_4\equiv a_2\pmod {m_2}，则根据性质 1，m_2\mid p_4。
• \cdots
• 若 p_n+p_1+p_2\equiv a_n\pmod {m_n}，则根据性质 1，m_n\mid p_2。

以此类推，直到出现 n 个数相加的情况。

整理一下，现在我们得到一些关于 p_1,p_2,\cdots,p_n 的余数信息：

• \cdots

这时发现，令 l=lcm(p_1,p_2,\cdots,p_n)，每一个 p_i 就是 \dfrac{l}{m_i} 的公倍数（p_i 是除了 m_i 外所有模数的倍数）。

然后再根据求三个数时候的方法对每一个 p_i 求出特殊解，相加后模 l 即可。

因为互质，所以 l=\prod\limits_{i=1}^{n}m_i（这个符号是累乘）。

最后分析一下复杂度：枚举 + 扩欧，时间复杂度 O(n\log n)。

代码

模板题：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 是真的模板。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10 + 10;
int n, lcm = 1, ans, a[N], m[N];//m[i] 模数，a[i] 余数 

void exgcd(int a, int b, int &x, int &y){//扩欧，记得带地址符 
    if(!b){
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, x, y);
    int lx = x, ly = y;
    x = y, y = lx - a / b * ly;
}

main(){
    scanf("%lld", &n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld", &m[i], &a[i]);
        lcm *= m[i];
    }
    for(int i=1;i<=n;i++){
        int x, y, li = lcm / m[i];//pi 是 li 的倍数
        exgcd(li, m[i], x, y);
        x *= li * a[i];//你懂得 
        (ans += x) %= lcm;//先取模，最后再处理答案 
    }
    ans = (ans % lcm + lcm) % lcm;//处理答案 
    printf("%lld\n", ans);
    return 0;
}

极其简短且好记，但是重在弄懂原理。

Part 2：扩展中国剩余定理（EXCRT）

仍然解决的是形如：

的方程组的情况，只不过这次 m_1,m_2,\cdots,m_n 并不一定互质。

显然上述方法并不可行且没有太多优化空间，只能考虑新方法。

考虑若只有两个方程组：

设 x=k_1m_1+a_1=k_2m_2+a_2。

合并后两个式子，m_1k_1-m_2k_2=a_2-a_1。

此时根据裴蜀定理，若 \gcd(m_1,m_2)\nmid a_2-a_1，则方程无解，否则可用扩欧求得 k_1,k_2，进而求出 x。

但我们要最小化 x，所以我们要最小化 k_1。根据方程组解集的规律，k_1 的通解为 k_1+t\cdot \dfrac{m_2}{\gcd(m_1,m_2)}，所以 k_1 的最小解 k_0=k_1\bmod \dfrac{m_2}{\gcd(m_1,m_2)}。

然后我们的这两个方程等价于 x\equiv m_1k_0+a_1\pmod {lcm(m_1,m_2)}。

这个方程看起来没什么用，因为它在说废话。

但是如果现在有 n 个方程，我们就可以用上面的式子合并了。

也就是说，exCRT 的核心思想就是两两方程合并。

void exgcd(ll a, ll b, ll &x, ll &y){
    if(!b)
        return x = 1, y = 0, void();
    exgcd(b, a % b, x, y);
    ll xx = x, yy = y;
    x = yy, y = xx - (a / b) * yy;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld", &a[i], &b[i]);
    ll nowa = a[1], nowb = b[1];
    for(int i=2;i<=n;i++){
        ll x, y, g = __gcd(a[i], nowa);
        exgcd(nowa, a[i], x, y);//y 用不到，只取 x 
        x *= (b[i] - nowb) / g;
        x = (x % (a[i] / g) + (a[i] / g)) % (a[i] / g);
        y = nowa * x + nowb;
        nowa = lcm(a[i], nowa);
        nowb = (y % nowa + nowa) % nowa;
    }
    printf("%lld\n", nowb);
    return 0;
}

加个乘法改加法，防溢出，即可过洛谷板子 P4777。