为何用C++计算组合数nCr时，部分输入（如30 15）结果为0？

问题代码 #

#include <iostream>
using namespace std;

int factorial(int num){       
unsigned long long int fact=1;
for (int i = num; i >=1; i--)
{
    fact=fact*i;
}
return fact;
}

int main()
{
unsigned long long int n,r,value;
cout<<"Enter a number whose nCr value is to be calculated (n and r respectively): ";
cin>>n>>r;
 unsigned long long int a=factorial(n);
 unsigned long long int b=factorial(r);
 unsigned long long int c=factorial(n-r);
 value=a/(b*c);
 cout<<"The value of nCr is : "<<value;
 return 0;
}

核心原因分析 #

• 返回类型不匹配导致数值截断：factorial函数内部用unsigned long long存储阶乘结果，但返回类型是int。当num≥13时，13!的结果（6227020800）已经超过普通int的最大值（通常为2147483647），此时返回值会被强制截断为错误的int值，后续用这个错误值计算组合数必然得到错误结果。

• 大阶乘触发无符号整数溢出：即使把factorial的返回类型改为unsigned long long，30!的数值（约2.65×10³²）远大于unsigned long long的最大值（约1.8×10¹⁹）。无符号整数溢出后会按模2⁶⁴规则循环，得到完全错误的数值。用这些溢出后的错误值计算a/(b*c)时，就会出现结果为0的情况。

优化思路（可选） #

避免直接计算完整阶乘，改用递推式分步计算组合数，减少溢出风险：

unsigned long long nCr(unsigned long long n, unsigned long long r) {
    if (r > n - r) r = n - r; // 利用对称性减少计算量
    unsigned long long result = 1;
    for (int i = 1; i <= r; ++i) {
        result = result * (n - r + i) / i;
    }
    return result;
}

这种分步乘除的方式，能有效控制中间结果的大小，同时保证计算精度。

内容的提问来源于stack exchange，提问作者user19612651