組合數計算：C(M,N)階乘公式與大整數處理的C語言實現

問題描述

計算組合數 C(M,N) = M! / (N! × (M-N)!)。輸入 T (≤10) 組測試數據，每組 N, M (≤20)。輸出每組結果。

階乘計算與溢出處理

20! = 2,432,902,008,176,640,000 超過 32 位整數，需 64 位。C 語言使用 `__int64` (MSVC) 或 `long long` (GCC)。

代碼實現

#include <stdio.h>

long long factorial(int a);

int main() {
    int num, n, m;
    scanf("%d", &num);

    while (num--) {
        scanf("%d %d", &n, &m);
        printf("%lld", factorial(m) / factorial(n) / factorial(m-n));
        if (num > 0) printf("\n");
    }
    return 0;
}

long long factorial(int a) {
    long long sum = 1;
    for (int i = 1; i <= a; i++) sum *= i;
    return sum;
}

優化：避免大數中間值

利用 C(M,N) = C(M, M-N) 取較小者；分子分母約分計算，避免階乘溢出風險（雖 20! 在 64 位內安全）。

測試樣例

輸入：

2
3 5
1 20

輸出：

10
20

C(5,3)=10；C(20,1)=20。