『壹』 中國剩餘定理 —— 霸氣的名字讓我對這個演算法產生了好感
當初探索演算法，純粹是因為它的名字——中國剩餘定理，也被稱為孫子定理。對這個演算法感興趣的朋友可以自行查閱它的原始名稱。接下來，讓我們深入探討這個演算法的精髓。
一、物不知數
【例題1】有一個未知數量的物品，當被三除時餘二，被五除時餘三，被七除時餘二。請問這個物品的數量是多少？
這個問題是中國南北朝時期《孫子算經》中的經典問題，被稱為「物不知數」問題。翻譯成現代語言，即尋找一個整數，它除以3餘2，除以5餘3，除以7餘2。用數學表達式表示為：[公式]，其中[公式]是公共的未知數。這種形式的方程組稱為同餘方程組，而[公式]就是這個同餘方程組。
二、同餘方程組
我們將同餘方程組表示為更一般的形式：[公式]。我們知道，同餘方程可以表示為等式的形式，因此同餘方程組也可以表示為：[公式]。在這種情況下，有[公式]個方程和[公式]個未知數。在存在解的情況下，可能存在無窮多解。
1、不存在解
當存在[公式]和[公式]，同時滿足[公式]且[公式]時，解必然是不存在的。因為任何數模另一個數的結果是確定的，不可能有兩種結果。
2、存在無窮多解
一旦存在解，對於任意兩個[公式]和[公式]，只要[公式]，必然滿足[公式]。出現這種情況時，變數數和方程數同時減少，未知數永遠比方程數多1，從而一定有無窮多解。
三、樸素演算法
樸素演算法採用窮舉的方法，以「物不知數」問題為例，我們可以從零開始枚舉[公式]的值，不斷試除，直到找到滿足三個同餘方程同時成立的整數。對於這個特定問題，它形成了一個等差數列，並且公差是105，即所有模數的乘積。因此，我們猜測同餘方程組的通解為：[公式]，其中最小的非負整數解為[公式]。
四、中國剩餘定理
根據上述猜測，模數不互素的情況包含模數互素的情況。因此，我將直接介紹模數不互素情況下同餘方程組通解的求解方式，即所謂的擴展中國剩餘定理。雖然它沒有「中國剩餘定理」這個名字霸氣，但重要的是理解演算法原理。我們給同餘方程組編號，並嘗試合並第[公式]個方程和第[公式]個方程，得到新的同餘方程。通過擴展歐幾里德定理，我們可以求出最小的正整數解，並得到最終的通解。
五、演算法實現
首先，設計一個類來表示方程，包含模數和余數。然後實現求解過程，包括標准化方程組、合並方程、利用擴展歐幾里得定理求解等步驟。最終，演算法將給出同餘方程組的最小非負整數解。