X=bi(mod ai) （1<=i<=n)。
首先为了解这个方程组，我们得证明这个方程必定有解，而证明这个方程必定有解以及这个方程的最小非负整数解的范围的确定，则需要用到中国剩余定理，又叫孙子定理，又叫中国余数定理.....
*以下来自算法导论君..
设整数N=n1*n2*n3*n4...，其中因子们两两互质（成立的关键）,首先，中国余数定理是一个描述性的结构定理（就是这个定理使用了一种新的结构来表示一个数）（这个结构就是取一个数对许多个质数取模的结果来表示这个数），它等同于用笛卡尔积Zn1*Zn2*Zn3...*Znk的结构描述Zn的结构（看不懂可以跳过..Zn是模运算下的循环群之类的....)，则我们有：
（中国余数定理）：令n=n1*n2*n3*..*nk，其中因子ni两两互质，考虑以下对应关系：
a<---->(a1,a2,a3,a4...,ak)即
ai=a(mod ni)（0<i<=k)（k为n分解质因数的个数）
这种用模表示一个数与直接在模n的情况下用十进制表示一个数是一一对应的（就是唯一的）。即我们知道了一个数模ni的不同余数，然后ni两两互质，n为ni的乘积，那么在0..n-1内这种用模表示的方法是唯一对应一个数的，这就是中国剩余定理。
拥有了这个定理（先无视怎么证得）,我们就可以肯定在n1*n2*n3...*ni的范围内解是唯一的，所以最小解也在这个范围内。
那么问题就是如何对这两种表示方法进行转化。
从a------------->(a1,a2,a3,a4..ak)非常简单，直接mod ni就可以了。
然后从 (a1,a2,a3,a4....ak)--------------------->a，就是我们现在想做的事情....这比较麻烦，我们可以构造出一个答案出来。
1)首先我们计算 n1*n2*n3*n4*...ni=n，则根据中国剩余定理解就在这个范围里面
2)然后我们设 mi=n div ni，求出 mi 模 ni的逆元u（这个扩展欧几里得（另外由于ni两两互质，必有逆元））
3)然后我们设ci=mi *u
4）最后答案就是 a=sigma(ci*ai) mod n
=（c1*a1+c2*a2+c3*a3...+ck*ak)mod n
为什么这样是对的呢？
我们可以证明嘛...
怎么证明呢？
直接证这个答案a满足所有的方程就可以了吧....
比如对于ni ，原方程是 a mod ni =ai
我们证这个是对的。代入a的表达式
a=(c1*a1+c2*a2+c3*a3...+ci*ai..+ck*ak)mod ni
由于c1=m1*u1(逆元）
而m1中必包含ni，所以c1模ni的值为0
以此类推，最后只有ci*ai mod ni的值不为0
而 ci*ai mod ni=(mi *ui) * ai mod ni，根据逆元的定义
mi*ui mod ni=1，
则化简为 a=ai mod ni
然后就OK啦~~~~~
码代码：
扩展欧几里得：
procedure exgcd(a,b:int64;var x,y:int64)
var s,t:int64;
begin
if b=0 then begin x:=1;y:=0;exit;end;
exgcd(b,a mod b,s,t);
x:=t;
y:=s-(a div b)*t
end;
然后就是求解(伪代码）
for i:=1 to n do n:=n * n[i];
for i:=1 to n do
begin
m[i]:=n div n[i];
exgcd(m[i],n[i],u,v)
u:=u mod n[i];
c[i]:=m[i]*u
end;
ans:=0;
for i:=1 to n do
ans:=(ans+c[i]*a[i])mod n
print ans
评论