计算nCr模p，素数

我试图计算nCr模p，其中p是素数。计算nCr模p，素数

我试过的一种方法是计算n！ /（r！*（n-r）！）模p使用乘法倒数，但是当r或n - r大于或等于p时，失败，因为那么因子是零模p并且倒数不存在。

什么方法适用于所有情况，而不仅仅是当乘法反转存在时？

2015-04-04 Ashwini

“对于每个大于p的n，该算法将给出nCr = 0，因为mod的阶乘将变为零。但这是错误的计算。防爆。 14C1 mod 13 = 1而不是0“你怎么用0算法得到0？ – IVlad 2015-04-04 08:28:24

'f [n] *（（InverseEuler（f [r]，p）* InverseEuler（f [nr]，p））％p ））％p';其中'f [n]是（n！％p）'和InverseEuler（a，b）是'（（a ^（p-2））％p）'这将是离散公式对于nCr，使用欧拉定理的模乘法逆，当n> = p时，f [n]将为零，因此nCr的值将变为零，如果我错了，就纠正我@IVlad – Ashwini 2015-04-04 09:22:17

该公式只适用于'f [x]，p' coprime。'p'的倍数与'p'不是互斥的。 – IVlad 2015-04-04 09:41:36

我最好使用Lucas's theorem

C(14,1), p=13 
N = 14 = 1 * 13 + 1 
K = 1 = 0 * 13 + 1 
C(N,K) mod p = (C(1,0) mod 13) * (C(1,1) mod 13) = 1

来源

2015-04-04 09:35:10 MBo

这就是我需要的确切的东西.... 。感谢很多@MBo – Ashwini 2015-04-04 19:52:08

计算nCr的模p，p是素数

预计算出n模p的使用
事实[n]的阶乘= N * fact [n-1]％p
预计算n模p的阶乘的倒数，使用
invfact [N] = modular_inverse（N）* INFACT [N-1]％P

modular_inverse可以通过使用Fermat's little theorem或Extended Euclidean algorithm被容易地发现。（由于p是素数都可以使用）
通过乘法实际上获取无碳复写纸[N] * INFACT [R] * INFACT [NR]％p

另一种方法：您还可以使用帕斯卡的方法来计算nCr的

如，对于任何nCr的，则可以使用

row[0]=1; 
for(i=1;i<n/2;i++) 
{ 
    row[i]=row[i-1]*(n-i+1)/i 
} 

for(i=n/2;i<=n;i++) 
{ 
    row[i]=row[n-i] 
}

在此可以选择使用上述任何方式（Fermat's little theorem或Extended Euclidean algorithm）

参考采取的（ⅰ）modulo_inverse： Best known algos for calculating nCr % M

来源

2015-09-08 21:15:28

计算nCr模p，素数

回答

相关问题