中国剩余定理（CRT）学习笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了中国剩余定理（CRT）学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

约定

\(A\perp B\) 表示 \(\gcd(A,B)=1\)。
\(A\mid B\) 表示 \(B\equiv 0\pmod{A}(A\neq0)\)。

引入

考虑以下这道题：

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？—— 《孫子算經》

也就是说，求出下列关于 \(x\) 方程组的最小整数解：

\[\begin{cases} x\equiv2\pmod{3}\\ x\equiv3\pmod{5}\\ x\equiv2\pmod{7} \end{cases} \]

解析

首先我们考虑什么时候 \(\equiv3\pmod{3}\)，什么时候 \(\equiv3\pmod{5}\)，什么时候 \(\equiv2\pmod{7}\)。也就是解下面的方程：

\[\begin{cases} x_1\equiv2\pmod{3}\\ x_2\equiv3\pmod{5}\\ x_3\equiv2\pmod{7} \end{cases} \]

解得：

\[\begin{cases} x_1=3k_1+2&(k_1\in\mathbb{Z})\\ x_2=5k_2+3&(k_2\in\mathbb{Z})\\ x_3=7k_3+2&(k_3\in\mathbb{Z})\\ \end{cases} \]

但这个解毫无用处。因为我们无法直接从 \(x_1,x_2,x_3\) 求出 \(x\)。

一种常见的想法是，取 \(x=x_1+x_2+x_3\)。那我们就有结论 \(x_1+x_2\equiv2\pmod{3}\)。

这个结论显然只在 \(3\mid x_2\) 时成立。

因此我们可以得到，令 \(x_1=(5\cdot7)y_1,x_2=(3\cdot7)y_2,x_3=(3\cdot5)y_3\)，则：

\[\begin{cases} 35y_1\equiv2\pmod{3}\\ 21y_2\equiv3\pmod{5}\\ 15y_3\equiv2\pmod{7} \end{cases} \]

然后发现 \(\equiv\) 右边的数字不是 \(1\) 就非常烦。我们令 \(z_1=2y_1,z_2=3y_2,z_3=2y_3\)，再分别约去 \(2,3,2\) 得到：

\[\begin{cases} 35z_1\equiv1\pmod{3}\\ 21z_2\equiv1\pmod{5}\\ 15z_3\equiv1\pmod{7} \end{cases} \]

注意到 \(3\perp5\perp7\)，则 \(35\perp3,21\perp5,15\perp7\)。所以存在逆元（存在 \(z_1,z_2,z_3\)）。这个可以用扩展欧几里得或者线性求逆元来求出 \(z_1=2,z_2=1,z_3=1\)。

则 \(y_1=4,y_2=3,y_3=2\)。\(x_1=140,x_2,=63,x_3=30\)。则 \(x=233\)。

但是 \(233\) 并不是最小正整数解。不难发现只要 \(a\equiv b\pmod{3\cdot5\cdot7}\)，那么 \(a,b\) 都是合法解。

所以最小正整数解是 \(233\bmod (3\cdot5\cdot7)=23\)。

整理

现在，我们就得到了求解下列方程组的通法：

\[\begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\cdots\cdots\cdots\cdots\cdot\cdot\\ x\equiv b_n\pmod{a_n}\\ \end{cases} \]

其中 \(a_1\perp a_2\perp\cdots a_n\)。

求出 \(K=\prod_{i=1}^{n}a_i\)。
对于 \(1 \leq i \leq n\)，解关于 \(z_i\) 的方程 \(\dfrac{K}{a_i}\cdot z_i\equiv1\pmod{a_i}\)。
计算 \(y_i=b_i\cdot z_i \cdot \dfrac{K}{a_i}\)。
则最小整数解 \(x=\sum_{i=1}^{n}{y_i} \bmod K\)。

例题

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

给出两个长为 \(n\) 的序列 \(a,b\)。求以下关于 \(x\) 的方程组的最小整数解：

\[\begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\cdots\cdots\cdots\cdots\cdot\cdot\\ x\equiv b_n\pmod{a_n}\\ \end{cases} \]

\(1 \leq n \leq 10\)

模板题。大家可以参考一下我的代码实现：文章来源地址https://www.toymoban.com/news/detail-429277.html

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

void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
	}
	else{
		exgcd(b,a%b,x,y);
		int tmp=x;
		x=y;
		y=tmp-a/b*y;
	}
}

int n,a[15],b[15];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    int K=1,x=0;
    for(int i=1;i<=n;i++) K*=a[i];
    for(int i=1;i<=n;i++){
        int z=0,ytxy=0,y=0;
        exgcd(K/a[i],a[i],z,ytxy);
        z=((z%a[i]+a[i])%a[i]);
        y=b[i]*z*(K/a[i]);
        x+=y;
    }
    cout<<((x%K+K)%K);
    return 0;
}

到了这里，关于中国剩余定理（CRT）学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！