c++ - 计算组合时溢出

Question

我试图在 C++ 中计算组合 C(40, 20)，但是 C++ 中的数据类型似乎无法正确处理此计算，即使我使用了 long long 数据类型。以下是我的代码:

#include <iostream>

long long fac(int x) {
    register long long i,f = 1; // Optimize with regFunction
    for(i = 1;i <= x;i++)
        f *= i;
    std::cout << f << std::endl;
    return f;
}

// C(n,r) = n!/r!(n-r)!
long long C(long long n, long long r) {
    return fac(n) / (fac(r) * fac(n - r));
}

int main(int argc, char const *argv[]) {
    std::cout << C(40, 20) << std::endl;
    return 0;
}

有解决这个问题的想法吗？

Answer 1

通过在乘法之后立即执行除法来立即计算 C:

long long C(long long n, long long r) 
{
    long long f = 1; // Optimize with regFunction
    for(auto i = 0; i < r;i++)
        f = (f * (n - i)) / (i + 1);
    return f ; 
}

结果应该是精确的(没有余数的除法，直到溢出)因为 (i+1) 中存在的任何整数因子已经存在于 (n -i) 中。 (应该不太难证明)