c++ - 我如何计算 k 取模 100003 中的大数的 n 的组合？

Question

n 的最大值是 100 000，k 可以是 0 到 100 000 之间的任何值。问题要求计算值对 100 003 取模。所以我使用了一个函数来计算 n、n-k 和 k 的阶乘然后打印 fact(n)/(fact(n-k)*fact(k))% 100 003。我做错了什么，解决方案是什么？

    long long int fact (int z)
{
    long long int r;
    if(z<=1)return 1;
    r=1LL*z*fact(z-1);
    return r;
}

Answer 1

long long 不够大，无法容纳有趣的 n 的 fact(n)，因此您需要更智能的算法。

在乘法时应用 mod 100003 是将事物保持在范围内的简单方法。但是模块化划分是困惑的，在这种情况下是不必要的。

考虑如何计算 fact(n)/( fact(n-k)*fact(k) ) 而无需除以任何大数或模数。