约定
-
\(A\perp B\ 表示 \(\gcd(A,B=1\。
- \(A\mid B\ 表示 \(B\equiv 0\pmod{A}(A\neq0\。
引入
有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。 問物幾何？—— 《孫子算經》
\[\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\。
这个结论显然只在 \(3\mid x_2\ 时成立。
\[\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}
\]
则 \(y_1=4,y_2=3,y_3=2\。\(x_1=140,x_2,=63,x_3=30\。则 \(x=233\。
所以最小正整数解是 \(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\。
-
对于 \(1 \leq i \leq n\，解关于 \(z_i\ 的方程 \(\dfrac{K}{a_i}\cdot z_i\equiv1\pmod{a_i}\。
-
则最小整数解 \(x=\sum_{i=1}^{n}{y_i} \bmod K\。
例题
P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
\[\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\
模板题。大家可以参考一下我的代码实现：
#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;
}