解题思路

这道题要求计算组合数 ( C(n, k) )，即从 ( n ) 个不同元素中选取 ( k ) 个元素的组合数。由于题目强调 中间结果可能溢出，因此不能直接计算阶乘，而应该采用 递推优化 或 动态规划 的方式，边乘边除，避免大数计算。

关键点

1. 组合数公式： [ C(n, k) = \frac{n!}{k! \cdot (n-k)!} ]
2. 优化计算：
   • 利用 组合数的对称性 ( C(n, k) = C(n, n-k) )，减少计算量。
   • 边乘边除，避免直接计算大阶乘，防止溢出。
3. 边界情况：
   • ( k = 0 ) 或 ( k = n ) 时，( C(n, k) = 1 )。
   • ( k > n ) 时，( C(n, k) = 0 )（但题目保证 ( 0 \leq k \leq n )）。

C++ 代码实现

#include <iostream>
#include <algorithm> // 用于 min 函数

using namespace std;

// 计算组合数 C(n, k)，避免中间结果溢出
long long comb(int n, int k) {
    if (k > n - k) {
        k = n - k; // 利用对称性减少计算次数
    }
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i; // 边乘边除，防止溢出
    }
    return res;
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        if (n == 0 && k == 0) {
            break;
        }
        cout << comb(n, k) << endl;
    }
    return 0;
}