我们如何计算N选择K模数为素数而不溢出？

Question

如何在不调用溢出的情况下在C或C++中计算机(N选择K)%M？

对于N(4 <= N <= 1000)和K(1 <= K <= N)且M = 1000003的特定情况.

Answer 1

要计算(n选择k)%M,你可以分别计算分母(n!)模数M和分母(k!*(n - k)!)模数M,然后将分母乘以分母的模乘法逆(在M).由于M是素数,你可以使用费马的小定理来计算乘法逆.

在以下链接上有一个很好的解释,带有示例代码(问题SuperSum):

对于一些额外的速度,将分子计算为从(K + 1)到N的分数,分母为K !. 我们知道在计算中不存在M的任何因子,因为它是素数且大于N.因此我们可以取消顶部和底部而不用担心我们取消的可能是M的倍数(即0). (2认同)