計算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，素數

回答

相關問題