韓信點兵：千年古算題的 Java 程式化解法

韓信點兵：千年古算題的 Java 程式化解法

「韓信點兵」源自一千多年前的《孫子算經》，原題為：「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」換句話說，求一個整數，除以 3 餘 2，除以 5 餘 3，除以 7 餘 2。這正是中國古代數學的經典同餘問題，也是《孫子算經》的開篇之作，後世稱為「孫子定理」或「中國剩餘定理」。

數學原理回顧

根據中國剩餘定理，若模數兩兩互質，則同餘方程組有唯一解（模 M = 3×5×7 = 105）。解法步驟：

1. 計算 M = 105，分別求 M₁=35, M₂=21, M₃=15。
2. 求各模數的乘法逆元：35×2≡1(mod3)、21×1≡1(mod5)、15×1≡1(mod7)。
3. 解 x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 = 233 mod 105 = 23。

最小正整數解為 23，通解為 23 + 105k (k∈N)。

Java 程式實現

雖然原文圖片不可見，但我們可以用暴力搜尋或構造法實現：

public class HanXinCounting {
    public static void main(String[] args) {
        // 方法一：暴力搜尋（適合小範圍）
        for (int i = 1; i <= 1000; i++) {
            if (i % 3 == 2 && i % 5 == 3 && i % 7 == 2) {
                System.out.println("最小解：" + i); // 輸出 23
                break;
            }
        }
        
        // 方法二：構造法（高效，適用於大數）
        int m1 = 35, m2 = 21, m3 = 15;
        int inv1 = 2, inv2 = 1, inv3 = 1; // 逆元
        int x = (2 * m1 * inv1 + 3 * m2 * inv2 + 2 * m3 * inv3) % 105;
        System.out.println("構造法解：" + x); // 輸出 23
    }
}

拓展思考

這道題不僅是算法面試常客，更展示了數論在計算機科學中的應用。現代密碼學（如 RSA）同樣依賴模運算與同餘原理。若模數不互質，需用擴展中國剩餘定理（EXCRT）處理，這在競賽編程中較常見。