algorithm - 解释以下算法以求 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) 可能会返回 n! 素因式分解中 p 的指数。如果get_degree(n, p) == get_degree(k, p) + get_degree(n - k, p)，那么p在分子和分母中的因式刚好抵消，我们可以用factMod 来考虑其他因素。否则，组合的数量可以被 p 整除，所以我们返回 0。

从 (p-1) 开始! ≡ -1 mod p by Wilson's theorem ，第一个内循环是多余的。