## 中国剩余定理 #### 问题： 设有k个素数m1…..mk,有某一个整数取模mi(1<=i<=k)结果为bi…bk,求这一个整数且是最小的。 思路：对于每一个因子mi构造，去构造一个数xi使得xi%mi==bi， xi%mj==0且j！=i。就是单纯构造一个只对mi有影响而对mj（j！=i）没有影响的数，这样∑xi一定是满足要求的数，但不一定是最大的，只要减去对所有m都没影响的部分就可以使结果最小。 #### 公式： M=∑mi； Result=[∑ (M/mi)*c]%M,其中1<=i<=k，c为一个整数，使[(M/mi)*c]%mi=bi。c可以从1开始去寻找，一定可以找到一个满足条件的整数。因为(M/mi)%mi必不为0，于是(M/mi)*c的余数会随着c的变化而变化，因此肯定存在一个这样的c，我们只需要找最小的即可。