中国剩余定理与韩信点兵问题的C++实现

1. 韩信点兵问题背景解析

韩信点兵是中国古代著名的数学问题，最早记载于《孙子算经》。问题描述为：韩信带兵时，让士兵按3人一排、5人一排、7人一排排队，每次都会剩余一定数量的士兵。通过观察这些余数，就能快速计算出士兵的总人数。

这个问题在数学上对应着"中国剩余定理"（Chinese Remainder Theorem, CRT）的应用场景。中国剩余定理指出：对于两两互质的整数n1,n2,...,nk，给定任意整数a1,a2,...,ak，存在唯一解x满足x ≡ ai mod ni（i=1,2,...,k），且解在模N=n1n2...nk下唯一。

2. 问题数学建模

假设：

• 士兵总数：x
• 3人一排余a人：x ≡ a mod 3
• 5人一排余b人：x ≡ b mod 5
• 7人一排余c人：x ≡ c mod 7

需要求解满足上述同余式的最小正整数x。

3. C++实现思路

3.1 暴力枚举法

最直观的解法是从1开始逐个验证，直到找到满足条件的数：

cpp复制int findSoldiers(int a, int b, int c) {
    for (int x = 1; ; x++) {
        if (x % 3 == a && x % 5 == b && x % 7 == c) {
            return x;
        }
    }
}

这种方法简单但效率低，时间复杂度为O(N)。

3.2 中国剩余定理优化解法

根据中国剩余定理，可以构建更高效的解法：

1. 计算模数乘积：N = 3×5×7 = 105
2. 计算各模数的商：
   • N1 = N/3 = 35
   • N2 = N/5 = 21
   • N3 = N/7 = 15
3. 求各Ni关于ni的模逆元：
   • 35 mod 3的逆元：35 ≡ 2 mod 3，2×2 ≡ 1 mod 3 → 逆元为2
   • 21 mod 5的逆元：21 ≡ 1 mod 5 → 逆元为1
   • 15 mod 7的逆元：15 ≡ 1 mod 7 → 逆元为1
4. 计算解：x = (a×N1×e1 + b×N2×e2 + c×N3×e3) mod N

C++实现：

cpp复制in