韓信點兵問題：中國剩餘定理（CRT）經典實現

問題描述

已知一隊士兵：

• 3 人一排餘 a
• 5 人一排餘 b
• 7 人一排餘 c
• 總人數在 10 ~ 100 之間

求總人數，無解輸出 No answer。

數學原理：中國剩餘定理

模數 3,5,7 兩兩互質，解模 M=105 唯一。構造解：

x = (a*70 + b*21 + c*15) % 105
其中：
70 ≡ 1 (mod 3), 70 ≡ 0 (mod 5), 70 ≡ 0 (mod 7)
21 ≡ 0 (mod 3), 21 ≡ 1 (mod 5), 21 ≡ 0 (mod 7)
15 ≡ 0 (mod 3), 15 ≡ 0 (mod 5), 15 ≡ 1 (mod 7)

暴力枚舉法（題目範圍小適用）

#include <stdio.h>

int main() {
    int a, b, c, i;
    while (scanf("%d%d%d", &a, &b, &c) != EOF) {
        for (i = 10; i <= 100; i++)
            if (i%3==a && i%5==b && i%7==c) break;
        if (i <= 100) printf("%d\n", i);
        else printf("No answer\n");
    }
    return 0;
}

CRT 公式法（O(1)）

int x = (a*70 + b*21 + c*15) % 105;
if (x < 10) x += 105;  // 移至 [10,100] 或更高
if (x >= 10 && x <= 100) printf("%d\n", x);
else printf("No answer\n");

測試樣例

Input:  2 1 6  →  x = (140+21+90)%105 = 251%105 = 41  → 41
Input:  1 2 3  →  x = (70+42+45)%105 = 157%105 = 52  → 52

總結

• 範圍小（10~100）暴力枚舉最簡單、不易出錯
• CRT 公式適合大範圍或多次查詢
• 注意 No answer 大小寫與空格