约定
- (Aperp B) 表示 (gcd(A,B)=1)。
- (Amid B) 表示 (Bequiv 0pmod{A}(Aneq0))。
引入
考虑以下这道题:
有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。 問物幾何?—— 《孫子算經》
也就是说,求出下列关于 (x) 方程组的最小整数解:
xequiv2pmod{3}\
xequiv3pmod{5}\
xequiv2pmod{7}
end{cases}
]
解析
首先我们考虑什么时候 (equiv3pmod{3}),什么时候 (equiv3pmod{5}),什么时候 (equiv2pmod{7})。也就是解下面的方程:
x_1equiv2pmod{3}\
x_2equiv3pmod{5}\
x_3equiv2pmod{7}
end{cases}
]
解得:
x_1=3k_1+2&(k_1inmathbb{Z})\
x_2=5k_2+3&(k_2inmathbb{Z})\
x_3=7k_3+2&(k_3inmathbb{Z})\
end{cases}
]
但这个解毫无用处。因为我们无法直接从 (x_1,x_2,x_3) 求出 (x)。
一种常见的想法是,取 (x=x_1+x_2+x_3)。那我们就有结论 (x_1+x_2equiv2pmod{3})。
这个结论显然只在 (3mid x_2) 时成立。
因此我们可以得到,令 (x_1=(5cdot7)y_1,x_2=(3cdot7)y_2,x_3=(3cdot5)y_3),则:
35y_1equiv2pmod{3}\
21y_2equiv3pmod{5}\
15y_3equiv2pmod{7}
end{cases}
]
然后发现 (equiv) 右边的数字不是 (1) 就非常烦。我们令 (z_1=2y_1,z_2=3y_2,z_3=2y_3),再分别约去 (2,3,2) 得到:
35z_1equiv1pmod{3}\
21z_2equiv1pmod{5}\
15z_3equiv1pmod{7}
end{cases}
]
注意到 (3perp5perp7),则 (35perp3,21perp5,15perp7)。所以存在逆元(存在 (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) 并不是最小正整数解。不难发现只要 (aequiv bpmod{3cdot5cdot7}),那么 (a,b) 都是合法解。
所以最小正整数解是 (233bmod (3cdot5cdot7)=23)。
整理
现在,我们就得到了求解下列方程组的通法:
xequiv b_1pmod{a_1}\
xequiv b_2pmod{a_2}\
cdotscdotscdotscdotscdotscdotcdot\
xequiv b_npmod{a_n}\
end{cases}
]
其中 (a_1perp a_2perpcdots a_n)。
-
求出 (K=prod_{i=1}^{n}a_i)。
-
对于 (1 leq i leq n),解关于 (z_i) 的方程 (dfrac{K}{a_i}cdot z_iequiv1pmod{a_i})。
-
计算 (y_i=b_icdot z_i cdot dfrac{K}{a_i})。
-
则最小整数解 (x=sum_{i=1}^{n}{y_i} bmod K)。
例题
P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪
给出两个长为 (n) 的序列 (a,b)。求以下关于 (x) 的方程组的最小整数解:
[begin{cases}
xequiv b_1pmod{a_1}\
xequiv b_2pmod{a_2}\
cdotscdotscdotscdotscdotscdotcdot\
xequiv b_npmod{a_n}\
end{cases}
](1 leq n leq 10)
模板题。大家可以参考一下我的代码实现:
#include
#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>a[i]>>b[i];
int K=1,x=0;
for(int i=1;i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net