今兒偶爾無聊，看到一個叫做“中國剩余定理”的玩意，覺得煞是好玩，便寫一點總結 上題目先， 假設一個數（1）被3除余2，（2）被5除余4，（3）被7除余6，求滿足條件的最小整數 lcm(5, 7) 為35 35*2=70剛好除以3余數為1 lcm(3, 7) 為21 21*1=21剛好除以5余1 lcm(5, 3) 為15 15*1 = 15剛好除以7余1 接下來(70*2 +21*4 +15*6)%lcm(70, 21, 15) = 104 最終，104就是要求的結果。 下面，寫成數學公式 題目：假設一個數M分別被A, B, C相除余數為a,b, c，求滿足條件的最小整數(A, B, C, a, b, c均為正整數) 步驟1： 先求解LCM(B, C) = A' 給A'乘上適當的正整數Ka(從1開始遞增), A'*Ka%A = 1一旦成立就終止，令A'' = A'*Ka同理可求B'', C''定義同上 步驟2：求解LCM(A, B, C) 結果： 那麼最後結果可以表示為(A'' * a + B'' * b + C" * c)%LCM(A, B, C); 下面，用C++實現完整代碼 [cpp] #include <iostream> using namespace std; int GCD(int a, int b) { int tmp; if (a < b) return GCD(b, a); while (b) { tmp = b; b = a % b; a = tmp; } return a; } int LCM(int a, int b) { return a*b/GCD(a, b); } void GET2(int& K2, int K) { int i = 1; while (1) { if (K2 % K == 1) break; else K2 *= ++i; } } int main() { int A, A1, A2, B, B1, B2, C, C1, C2, a, b, c, i, D; cout << "分別輸入三個除數和余數: "; cin >> A >> a; cin >> B >> b; cin >> C >> c; //求解最小公倍數A', B', C' A2 = A1 = LCM(B, C); B2 = B1 = LCM(A, C); C2 = C1 = LCM(A, B); D = LCM(A1, A); //三個數的最小公倍數 //求解A'', B'', C'' GET2(A2, A); GET2(B2, B); GET2(C2, C); cout << "要求的數為: " << (A2 * a + B2 * b + C2 * c) % D << endl; return 0; }
