以下算法的說明找到nCr的模P

Question

我試圖解決涉及大量階乘模的首要問題，並找到了另一個解決方案如下算法：

long long factMod (long long n, long long p) 
{ 
    long long ans = 1; 
    while (n > 1) 
    { 
     long long cur = 1; 

     for (long long i = 1; i < p; i++) 
     { 
      cur = (cur * i) % p; 
     } 

     ans = (ans * modPow(cur, n/p, p)) % p; 


     for (long long i = 1; i <= n % p; i++) 
     { 
      ans = (ans * i) % p; 
     } 

     n /= p; 
    } 

    return (ans % p); 
} 

long long nChooseK(long long n, long long k, long long p) 
{ 
    int num_degree = get_degree(n, p) - get_degree(n - k, p); 
    int den_degree = get_degree(k, p); 
    if (num_degree > den_degree) { return 0; } 

    long long nFact = factMod(n, p); 
    long long kFact = factMod(k, p); 
    long long nMinusKFact = factMod(n-k, p); 

    long long ans = (((nFact * modPow(kFact, p - 2, p)) % p) * modPow(nMinusKFact, p - 2, p))%p; 
    return ans; 
} 

我知道數論的基礎知識但似乎無法弄清楚這是如何工作的。

nChooseK函數似乎使用組合[n！/（n-k）！k！]的定義與使用費馬小定理來代替除法的模逆算法。然而，根據其中一個答案，factMod函數並不實際計算階乘。如果是這種情況，nChooseK函數如何工作？

Answer 1

是的，n！ ≡ 0 mod p當且僅當n ≥ p，但factMod不計算n！ mod p –它計算n/p ^k mod p其中k是n的素因子分解中p的指數， 或許是 ，用於計算二項式係數。循環的迭代i（從0開始計數）計算那些因子的貢獻1 n其素因子分解包括p ⁱ。語句n /= p;產生p的倍數的子問題。

函數get_degree(n, p)可能返回p的指數在n！的素因式分解中。如果get_degree(n, p) == get_degree(k, p) + get_degree(n - k, p)，則分子和分母中的p因子完全取消，我們可以使用factMod來解釋其他因素。否則，組合的數量可以被p整除，所以我們返回0.

既然（p-1）！ ≡ -1 mod p Wilson's theorem，第一個內部循環是多餘的。