## 中國剩余定理 #### 問題： 設有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，我們只需要找最小的即可。