借15級上機的一道題數論の重逢來總結一下中國剩余定理

先舉一個小例子

問題：今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

說明白一點就是說，存在一個數x，除以3余2，除以5余三，除以7余二，然后求這個數。上面給出了解法。再明白這個解法的原理之前，需要先知道一下兩個定理。

定理1：幾個數相加，如果存在一個加數，不能被數a整除，那么它們的和，就不能被整數a整除。

定理2：兩數不能整除，若除數擴大（或縮小）了幾倍，而被除數不變，則其商和余數也同時擴大（或縮小）相同的倍數（余數必小于除數）。

現給出求解該問題的具體步驟：

• 求出最小公倍數(這里討論的都是兩兩互質的情況)

  lcm=3*5*7=105

• 求各個數所對應的基礎數

  觀察求每個數對應的基礎數時候的步驟，比如第一個。105÷3=35。顯然這個35是除了當前這個數不能整除以外都能夠被其他數整除，就是其他數的最小公倍數。相當于找到了最小的開始值，用它去除以3發現正好余2。那么這個基礎數就是35。

  105÷3=35

  35÷3=11……2 //基礎數35

  記住35的特征，可以整除其他數但是不能被3整除，并且余數是2。體現的還不夠明顯，再看下5對應的基礎數。21是其他數的最小公倍數，但是不能被5整除，用21除以5得到的余數是1，而要求的數除以5應該是余1的。所以余數被擴大，就得到了相應的基礎數63。

  105÷5=21

  21÷5=4……1

  定理2把1擴大3倍得到3，那么被除數也擴大3倍，得到21*3=63//基礎數63

  記住這個數的特征，可以被其他數整除但是被5除應該余三。同理，我們得到了第三個基礎數30，那么他的特征就是：可以被其他數整除，但是不能被7整除，并且余數為2。

  105÷7=15

  15÷7=2……1

  定理2把1擴大2倍得到2，那么被除數也擴大2倍，得到15*2=30//基礎數30

• 基礎數加和（注意：基礎數不一定就是正數）

  35+63+30=128

  對于3來說，可以把63+30的和看作一個整體，應該他們都可以被3整除。看著上面寫出的三個數的特征，運用定理1來說，就是在35的基礎上加上一個可以被3整除的倍數，那么得到的結果依然還是滿足原先的性質的，就是128除以同樣還是余2的。同理，對于5還說，這個數被除之后會剩余3；對于7來說，被除之后剩余2。所以說，我們當前得到的這個數是滿足題目要求的一個數。但是這個數是不是最小的，那就不一定了。

• 減去最小公倍數lcm（在比最小公倍數大的情況下）

  x=128-105=23

  應該不能確定是不是最小的數，這個時候就要用到他們的最小公倍數了。最小公倍數顧名思義，一定是一個同時被幾個數整除的最小的一個數，所以減去它剩余下來的余數還是符合題意要求的。當然也同樣可以運用定理1來解釋，只不過是加法變成了減法，道理還是一樣的。當然具體要不要減還是要看和lcm的大小關系的。

那么滿足題意得最小的數就是23了。

總之，就是已知m1,m2,m3是兩兩互質的正整數，求最小的正整數x，使它被m1,m2,m3除所得的余數分別是c1,c2,c3。孫子定理的思想便是線分別求出被其中數mi整除余1而被兩外兩個數整除的數Mi(i=1,2,3)，則所求數之一的便是c1M1+c2M2+c3M3。由此我們可以得到n個兩兩互質數的情況。證明上面已經一步一步給出。

那么對于這道題的代碼就是

// // main.cpp // 數論の重逢 // // Created by Angus on 2017/12/21. // Copyright ? 2017年 Angus. All rights reserved. //#include <iostream> #include <cstdio> #include <algorithm>using namespace std;//參數可為負數的擴展歐幾里德定理 void exOJLD(long long a, long long b, long long &x, long long &y){//根據歐幾里德定理if(b == 0){//任意數與0的最大公約數為其本身。x = 1;y = 0;}else{long long x1, y1;exOJLD(b, a % b, x1, y1);if(a*b < 0) {//異號取反x = - y1;y = a / b * y1 - x1;}else{//同號x = y1;y = x1 - a / b * y1;}} }//剩余定理 long long calSYDL(long long a[], long long m[], long long k){long long N[k];//這個可以刪除long long mm = 1;//最小公倍數long long result = 0;for(long long i = 0; i < k; i++){mm *= m[i];}for(long long j = 0; j < k; j++){long long L, J;exOJLD(mm / m[j], -m[j], L, J);N[j] = m[j] * J + 1;//1N[j] = mm / m[j] * L;//2 【注】1和2這兩個值應該是相等的。result += N[j] * a[j];}return (result % mm + mm) % mm;//落在(0, mm)之間，這么寫是為了防止result初始為負數，本例中不可能為負可以直接 寫成：return result%mm;即可。 }int main(int argc, const char * argv[]) {// insert code here...long long p, e, i;while(~scanf("%lld%lld%lld", &p, &e,&i)) {long long a[3] = {p, e, I};//余數long long m[3] = {25, 28, 33};//除數printf("%lld\n",calSYDL(a, m, 3));//余數數組，除數數組，數組元素個數}return 0; }

---

參考資料
中國剩余定理(孫子定理)詳解
中國剩余定理(孫子定理)的證明和c++求解

總結

以上是生活随笔為你收集整理的算法——中国剩余定理（孙子定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。