中国剩余定理（孙⼦定理）详解
问题：今有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。问物⼏何？
简单点说就是，存在⼀个数x，除以3余2，除以5余三，除以7余⼆，然后求这个数。上⾯给出了解法。再明⽩这个解法的原理之前，需要先知道⼀下两个定理。
定理1：两个数相加，如果存在⼀个加数，不能被整数a整除，那么它们的和，就不能被整数a整除。
定理2：两数不能整除，若除数扩⼤（或缩⼩）了⼏倍，⽽被除数不变，则其商和余数也同时扩⼤（或缩⼩）相同的倍数（余数必⼩于除数）。
以上两个定理随便个例⼦即可证明！
现给出求解该问题的具体步骤：
1、求出最⼩公倍数
lcm=3*5*7=105
2、求各个数所对应的基础数
（1）105÷3=35
35÷2 //基础数35
（2）105÷5=21
21÷5=4 (1)
定理2把1扩⼤3倍得到3，那么被除数也扩⼤3倍，得到21*3=63//基础数63
快乐靠自己3、105÷7=15
小三吴颖15÷7=2 (1)
定理2把1扩⼤2倍得到2，那么被除数也扩⼤2倍，得到15*2=30//基础数30
把得到的基础数加和（注意：基础数不⼀定就是正数）
35+63+30=128
4、减去最⼩公倍数lcm（在⽐最⼩公倍数⼤的情况下）
x=128-105=23
那么满⾜题意得最⼩的数就是23了。⼀共有四个步骤。下⾯详细解释每⼀步的原因。
（1）最⼩公倍数就不解释了，跳过（记住，这⾥讨论的都是两两互质的情况）
（2）观察求每个数对应的基础数时候的步骤，⽐如第⼀个。105÷3=35。显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最⼩公倍数。相当于到了最⼩的起始值，⽤它去除以3发现正好余2。那么这个基础数就是35。记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。体现的还不够明显，再看下5对应的基础数。21是其他数的最⼩公倍数，但是不能被5整除，⽤21除以5得到的余数是1，⽽要求的数除以5应该是余1的。所以余数被扩⼤，就得到了相应的基础数63。记住这个数的特征，可以被其他数整除但是被5除应该余三。同理，我们得到了第三个基础数23，那么他的特征就是：可以被其他数整除，但是不能被7整除，并且余数为2。
（3）第三步基础数加和，为什么要这样做呢？利⽤就是上⾯提到的定理1。
35+63+30=128。对于3来说，可以把63+30的和看作⼀个整体，应该他们都可以被3整除。看着上⾯写出的三个数的特征，运⽤定理1来说，就是在35的基础上加上⼀个可以被3整除的倍数，那么得到的结果依然还是满⾜原先的性质的，就是128除以同样还是余2的。同理，对于5还说，这个数被除之后
会剩余3；对于7来说，被除之后剩余2。所以说，我们当前得到的这个数是满⾜题⽬要求的⼀个数。但是这个数是不是最⼩的，那就不⼀定了。
（4）应该不能确定是不是最⼩的数，这个时候就要⽤到他们的最⼩公倍数了。最⼩公倍数顾名思义，⼀定是⼀个同时被⼏个数整除的最⼩的⼀个数，所以减去它剩余下来的余数还是符合题意要求的。当然也同样可以运⽤定理1来解释，只不过是加法变成了减法，道理还是⼀样的。当然具体要不要剪还是要看和lcm的⼤⼩关系的。
稍微的总结⼀下：就是已知m1,m2,m3是两两互质的正整数，求最⼩的正整数x，使它被m1,m2,m3除所得的余数分别是c1,c2,c3。孙⼦定理的思想便是线分别求出被其中数mi整除余1⽽被另外两个数整除的数Mi(i=1,2,3)，则所求数之⼀的便是c1M1+c2M2+c3M3。由此我们可以得到n个两两互质数的情况。证明上⾯已经⼀步⼀步给出。
那么，到此为⽌基本的中国剩余定理的内容我们以及了解了，包括解答⽅法。那么如何编码呢？按照上⾯这个思路去编码，其实并不难。⼀共分为四⼤步。但是，⼤多数⼈的困惑在于如何求取基础数。这⾥呢，提供两种⽅法：
（1）第⼀种就是⼀直递增，直到到。例如：3的基础数，35是其他数的最⼩公倍数。那么就从35开始，⼀直⾃增，直到余数为2，便停⽌（利⽤while循环）。
（2）第⼆种⽅法呢就是辗转相除法上得来的。这⾥的例⼦体现的不够明显，应当看看去求取乘法逆元的过程，下⾯讲的内容和乘法逆元有很⼤的关系，所以还是看看的好。简单举个例⼦：
假设现在三个数分别是14，3，5，它们两两互质，且要求的数除以5余3。求5对应的基础数。有：
42÷5=8 (2)
5÷2=2 (1)
所以1=5-2*2=5-2*（42-8*5）=-2*42+17*5
那么-2*42=-84  17*5=85  -84+85=1
把1扩⼤3倍变成3，则有-84*3=-252也就是5对应的基础数。
第⼀点：基础数可以是负数，这个之前点到过。//并且下⾯的解法就是有这样的。
第⼆点：当得到余数为1的时候后⾯的算式相当于是⼀个回溯的过程，最后解到-2*42。但是还只不过是余数是1的情况对应的数，再运⽤定理2我们就得到了-252这个基础数。实际上要是看过乘法逆元，这⾥实际就是乘法逆元的求解过程，⽽-2也就是42关于15取模的乘法逆元。
模板：
/*long long gcd(LL a,LL b)
{
刘洪悦老公
return b==0?a:gcd(b,a%b);
}*/
#include<cstdio>
#define ll long long
//扩展欧⼏⾥得算法
void gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==0){
d=a;
x=1,y=0;
}
else{//else不能省略
gcd(b,a%b,d,y,x);
y-=(a/b)*x;
}
}
//中国剩余定理
ll China(int n,ll *m,ll *a)
{
ll M=1,d,y,x=0;
for(int i=0;i<n;i++) M*=m[i];
for(int i=0;i<n;i++){
ll w=M/m[i];
gcd(m[i],w,d,d,y);北方的天空
x=(x+y*w*a[i])%M;
}
return (x+M)%M;
}
dancewithmyfatherll m[15],a[15];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
如果没有遇见你scanf("%lld%lld",&m[i],&a[i]);
printf("%lld",China(n,m,a));
}