对于同余方程组：
x=a1 （mod m1）； 1
x=a2 （mod m2）； 2
方程组有一个小于m（m1，m2的最小公倍数）的非负整数解的充分必要条件是（a1-a2）%（m1，m2）==0 ，同样利用扩展欧几里德算法。
两式联立：a1+m1*y=a2+m2*z。
则：a1-a2=m2*z-m1*y; 这样就可以了解出z和y，则：x=a2+m2*z；
：（设m1,m2,···,mk两两互素） PS：使用中国剩余定理的条件
x=a1（mod m1）;
x=a2（mod m2）;
···
M=m1*m2*···*mk;中有唯一整数解。
如果记ei=Mi*pi;那么：ei=0 （mod mj）,j!=i; ei=1（mod mj）,j=i;
很明显，e1*a1+e2*a2+···+ek*ak就是方程的一个解，加减M倍后就可以得到最小非负整数解了。（没看懂）
如果m1,m2,···,mk不互素，那只能两个两个求解线性同余方程组了。
x=a1 （mod m1）；
x=a2 （mod m2）；
.............
解完后，a=x； m=m1和m2的最小公倍数。即可。
PS:应用中国剩余定理解线性同余方程组的条件是m1,m2,···,mk两两互素,适用范围小于普通的方法解线性同于方程组。我没有看懂这个定理，所以我遇到题目的时候
会选择普通方法来求解，这个定理的结论暂且背下来。
令Mi=M/mi,因为m1,m2,m3...mr两两互素，因此（Mi,mi)=1;即MiPi==1(mod mi)。（==为同余的意思）
那么容易验证a1M1p1+a2M2p2+a3M3p3+......+arMrpr就是同余方程组的解。（这里pi需要利用扩展欧几里得求解出来）
下面给出求此类同余方程组最小非负整数解的算法实现。
int china(int r)
{
M=1;
for(int i=1; i<=r; i++)
M*=m[i];
for(int i=1; i<=r; i++)
{
Mi=M/m[i];
extend(Mi,m[i],d,X,Y);
ans=(ans+Mi*X*a[i])%M;
}
if(ans<0)
ans+=M;
return ans;
}POJ 1006:Biorhythms
中国剩余定理的直接应用。
根据题意可得
模版：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int X,Y,d,M;
int m[10],a[10];
void extend(int A,int B,int &d,int &x1,int &y1)
{
if(B==0)
{
x1=1;
y1=0;
d=A;
return ;
}
extend(B,A%B,d,x1,y1);
int temp=x1;
x1=y1;
y1=temp-(A/B)*y1;
return ;
}
int china(int r)
{
int ans=0,Mi;
M=1;
for(int i=1; i<=r; i++)
M*=m[i];
for(int i=1; i<=r; i++)
{
Mi=M/m[i];
extend(Mi,m[i],d,X,Y);
ans=(ans+Mi*X*a[i])%M;
}
if(ans<0)
ans+=M;
return ans;
}
int main()
{
int t,k = 0;
while(scanf("%d%d%d%d",&a[1],&a[2],&a[3],&t)!=EOF)
{
k++;
if(a[1]==-1 && a[2]==-1 && a[3]==-1 && t==-1)
{
break;
}
m[1]=23;
m[2]=28;
m[3]=33;
int ans=china(3);//m的数目
while(ans<=t)
ans+=M;
printf("Case %d: the next triple peak occurs in %d days.\n",k,ans-t);
}
return 0;
}HDU1788:
刷够了，先在这里存着吧，未完待续。15.1.21
Chinese remainder theorem again
我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的：
假设m1,m2,…,mk两两互素，则下面同余方程组：
x≡a1(mod m1)
x≡a2(mod m2)
…
x≡ak(mod mk)
在0<=<m1m2…mk内有唯一解。
记Mi=M/mi(1<=i<=k),因为（Mi,mi）=1,故有二个整数pi,qi满足Mipi+miqi=1,如果记ei=Mi/pi,那么会有：
ei≡0(mod mj),j!=i
ei≡1(mod mj),j=i
很显然，e1a1+e2a2+…+ekak就是方程组的一个解，这个解加减M的整数倍后就可以得到最小非负整数解。
这就是中国剩余定理及其求解过程。
现在有一个问题是这样的：
一个正整数N除以M1余(M1 - a)，除以M2余(M2-a), 除以M3余(M3-a),总之， 除以MI余(MI-a),其中（a<Mi<100 i=1,2,…I）,求满足条件的最小的数。
