今有物不知其数，三三数之余二；五五数之余三；七七数之余二。问物几何？
语文水平不高，大概翻译一下：
今天Rothen钓了几个妹子，3个3个的数会余下2个，5个5个的数会余下3个，七个七个的数会剩下2个
好吧，这样好像更难理解了,懒得翻译了，反正大家都看得懂，大佬们就先做会吧，反正对于您这种神犇那肯定是秒切啊！。
中国剩余定理？？？好高级的东西啊，吓得我赶紧来个BFS( Baidu First Search)
发现中国剩余定理又叫孙子定理，原因是孙子发明的（这名字绝了）
然后对于上面的题目的解法为：
(注意，中国剩余定理的解法只能用于几个模数两两互质的情况)
1.首先找出5和7的 mod 3等于1的公倍数(70)，然后找出3和7的mod 5 等于1的公倍数(21),还有就是3 和 5的mod 7等于1的公倍数(15)
2.答案就是上面求出来的三个数的乘积分别乘以"对应的余数" mod 所有模数的乘积 例如 (70*2+21*3+15*2)mod (7*3*5)得到23
纳尼！这么神奇的吗？
真的就是这么神奇哦～
本蒟蒻查阅对于这个定理的证明为：
把上面的问题转化为多个个子问题：
假设存在一个数x1 % 3 =2("%"就是取余数),那么x1就能表示为3k+2的形式(k >= 0)
假设存在一个数x2 % 5 =3("%"就是取余数),那么x1就能表示为5k+3的形式(k >= 0)
假设存在一个数x3 % 7 =2("%"就是取余数),那么x1就能表示为7k+2的形式(k >= 0)
那么考虑如果存在一个
x1 + x2 + x3使得它们满足上面的所有条件呢？
首先有个特别基础的公式：A % B = C, 那么(A + B*K) % B =C
这个应该很好理解，你可以这么想：跟上面的类似,A可以表示为 若干倍的B加上C，
而A+B*k就可以表示为：若干倍的B + C +K倍的B ，自然的对于(A+B*k)%B也是等于C了啊！
回到刚才的问题，怎么样才能使得x1+x2+x3满足条件呢？
若要使得(x1+x2+x3)%3仍然余下2，那么x2,x3就一定要是三的倍数
若要使得(x1+x2+x3)%5仍然余下3，那么x1,x3就一定要是五的倍数
若要使得(x1+x2+x3)%7仍然余下2，那么x1,x2就一定要是七的倍数
所以问题就转化为了求出x1,x2,x3
哦吼，从上面我们看出了x1,x2,x3的几个性质：
1.x1是5和7的公倍数，而且x1 % 3 = 2
2.x2是3和7的公倍数，而且x2 % 5 = 3
3.x3是3和5的公倍数，而且x3 % 7 = 2
同时又引入一个数学公式：
如果a%b=c,那么(a*k)%b=(a%b+a%b+a%b+...+a%b(k个a%b) ) mod b=c×k mod b
然后问题就可以用开篇的方法解决了呀！而且找出来的是最小满足条件的数。
妙啊！
例题：
P1495 【模板】中国剩余定理(CRT)/曹冲养猪
板子，不多赘述。
放上我这丑的一批的代码：
#include <bits/stdc++.h> #define int long long using namespace std; int n,a[15],b[15],c[15],q=1,sum=0; signed main(){ cin>>n; for (int i = 1 ; i <= n ; i ++) cin>>a[i]>>b[i],q*=a[i]; for (int i = 1 ; i <= n ; i ++){ if(a[i] == 1)continue; q/=a[i]; int j=1; while(q*j % a[i] != 1)j++;//找其他几个数的公倍数%a[i]等于一的数 c[i]=q*j; q*=a[i]; } for (int i = 1 ; i <= n ; i ++) sum+=c[i]*b[i],sum%=q; cout<<sum%q; return 0; }
注意：中国剩余定理只能用于每一个a[i]都两两互质的情况，但是如果它们不是两两互质的，我们就要用 “扩展中国剩余定理”
扩展中国剩余定理是中国剩余定理的"进阶版"
那么扩展中国剩余定理的使用情况是怎么样的呢？
因为上面也提到了：“注意，中国剩余定理的只能用于几个模数两两互质的情况”，所以扩展中国剩余定理就是可以适用于模数不两两互质的情况。
那这怎么搞啊？
聪明的数学家们又找到了一种办法：
将原来的余数方程列出来
假设现在我们已经求出来了前k-1个方程的解是x，现在加入了第k个方程
设前k-1个方程的模数的乘积是M，我们现在就是要求一个数字P使得
(x + P*M) % 第k个模数 = 第k个余数
这个P是可以通过扩展欧几里得算法算出来的，所以就可以很快求出P来。
这个问题又解决了，妙啊！