前置知识
乘法逆元
物不知数
问题：计算一个整数 x ，使得它满足除以3余2、除以5余3、除以7余2。
如果能够找到三个整数 x1,x2,x3 ，使得：
x1 除以3余2、除以5余0、除以7余0；
x2 除以3余0、除以5余3、除以7余0；
x3 除以3余0、除以5余0、除以7余2；
那么令 x=x1+x2+x3,就很容易验证这时的 x 就满足除以3余2、除以5余3、除以7余2。
分别称找到整数 x1,x2,x3 的问题为问题1、问题2、问题3。可以看出这三个问题本质上是类似的。
下面对问题1-1继续分解，如果能够找到一个整数 y1 满足 y1 除以3余1、除以5余0、除以7余0，那么令 x1=y1*2 ，就很容易验证这时的 x1 就满足除以3余2、除以5余0、除以7余0。
因此定义
问题1为：寻找整数 y1 满足 y1 除以3余1、除以5余0、除以7余0；
问题2为：寻找整数 y2 满足 y2 除以3余0、除以5余1、除以7余0；
问题3为：寻找整数 y3 满足 y3 除以3余0、除以5余0、除以7余1。
这三个问题本质上是相同的。
如果找到了 y1,y2,y3 ，那么就可以取 x=2*y1+3*y2+2*y3。
对问题1进行解析
易知可以通过乘法逆元求解 y1
则将此方法进行一般性推广，得到下列证明：
数学证明
代码
int ExGcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int ans=ExGcd(b,a%b,x,y);
int t=y;
y=x-(a/b)*y;
x=t;
return ans;
}
int inv(int a,int p)//无解返回 -1
{
int x,y;
if(ExGcd(a,p,x,y)!=1) return -1;
return (x%p+p)%p;//正数化
}
int CRT(int a[],int m[],int n)
{
int N=1,x=0;
for(int i=1;i<=n;++i) N*=m[i];
for(int i=1;i<=n;++i)
{
int r=N/m[i];
x+=(r * inv( r , m[i] ) * a[i])%N;
}
return x%N;
}
