在组合数取模问题中，我们熟悉的普通Lucas定理只能处理模数是质数的情况，如果模数不是质数，甚至不是质数的幂，普通Lucas定理就完全失效了。而扩展Lucas定理就是为了解决任意模数下组合数取模 C(n, m) mod p 的问题，不管p是不是质数，都能给出正确结果。

这篇笔记会从基础问题出发，一步步拆解扩展Lucas定理的推导和实现，带你彻底搞懂这个知识点。

一、前置知识：为什么需要扩展Lucas？

我们先回忆一下问题背景：我们要计算组合数 C(n, m) = n!/(m! * (n-m)!) 对 p 取模的结果。

• 如果 p 是质数，直接用普通Lucas定理就能解决，复杂度很低，实现也简单。

• 如果 p 不是质数，我们就要用扩展Lucas定理了。

那为什么普通Lucas不能用在合数模数上？核心原因在于：普通Lucas的推导依赖模数是质数时的二项式定理性质，当模数是合数时，这个性质不成立，而且分母的逆元也不一定存在（只有当分母和模数互质的时候逆元才存在），所以必须换一套思路处理。

二、核心思路：中国剩余定理拆分合并

扩展Lucas定理的整体思路非常清晰，就是拆分+合并：

1. 根据算术基本定理，把模数 p 分解质因数，写成 p = p1^k1 * p2^k2 * ... * pn^kn，其中每个 pi^ki 都是「质数的幂」，而且两两互质。

2. 对每个质数幂 pi^ki，分别计算 C(n, m) ≡ ai mod pi^ki，得到一组同余式。

3. 用中国剩余定理合并这组同余式，就能得到 C(n, m) mod p 的结果。

这个框架本身不难理解，最难的部分其实是第二步：怎么计算 C(n, m) mod p^k，其中p是质数，k≥1。我们接下来重点拆解这部分。

三、关键步骤：计算 C(n, m) mod p^k

我们知道 C(n, m) = n! / (m! * (n-m)!)，现在我们要对这个式子模 p^k，但问题在于：分母 m! 和 (n-m)! 可能包含因子 p，所以分母和 p^k 不互质，逆元不存在，没法直接求逆。

那我们怎么处理？思路很简单：把分子分母中所有的因子 p 都提出来，剩下的部分就和 p^k 互质了，就可以求逆了，最后再把提出来的p的指数补回去就好了。

我们把这个过程写得更具体一点：

1. 对于任意 n!，我们可以把它写成 n! = p^{x} * a，其中 a 和 p 互质，x 是 n! 中包含的p的总幂次。

2. 同理，我们可以把 m! = p^{x1} * a1，(n-m)! = p^{x2} * a2，都是a和p互质的形式。

3. 代入组合数，我们得到： $$ C(n, m) = \frac{n!}{m! \cdot (n-m)!} = \frac{p^{x} \cdot a}{p^{x1} a1 \cdot p^{x2} a2} = p^{x - x1 - x2} \cdot \frac{a}{a1 a2} $$ 这里 a/(a1*a2) 的分子分母都和p互质，所以分母一定和 p^k 互质，逆元存在，可以直接计算。

4. 最终我们得到： $$ C(n, m) \equiv p^{x - x1 -x2} \cdot a \cdot inv(a1) \cdot inv(a2) \pmod{p^k} $$

所以现在问题又拆成了两个小问题：

• 怎么求n!中p的幂次x？

• 怎么求去掉所有p因子之后n!模p^k的结果a？

我们一个个解决。

3.1 求 n! 中 p 的幂次：勒让德公式

这个问题其实有现成的结论：勒让德公式，n!中p的幂次等于： $$ x = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i} \rfloor $$ 原理很简单：1~n中每p个数就有一个是p的倍数，贡献至少一个p；每p^2个数就有一个是p^2的倍数，多贡献一个p；以此类推直到p^i >n，就可以停止了。

代码实现也非常简单，循环累加就好：

int get_p_power(int n, int p) {
   int res = 0;
   while (n > 0) {
       n /= p;
       res += n;
   }
   return res;
}


3.2 求去掉所有p因子之后 n! 模 p^k 的结果

这一步是扩展Lucas最巧妙的部分，我们用例子来推导，比如我们计算 n! 去掉所有p因子之后模 p^k，举个例子，p=3，k=2，p^k=9，n=10：

10! = 1×2×3×4×5×6×7×8×9×10
把里面所有3的倍数提出来：
= (1×2×4×5×7×8×10) × (3×6×9)
把第二个部分提出一个3：
= (1×2×4×5×7×8×10) × 3^(3) × (1×2×3)


现在看第一部分 1×2×4×5×7×8×10，我们看看模9的规律： 每p^k=9个数为一组，(1×2×4×5×7×8) ≡ (10×11×...×18去掉3的倍数) mod 9，也就是每一组的乘积模p^k都是一样的，这就是周期性！

我们把这个规律推广到一般情况：

• n!去掉所有p因子后，可以分成三部分：

1. 周期部分：每 p^k 个数为一个周期，每个周期内去掉p的倍数后的乘积模 p^k 是相同的，一共 floor(n / p^k) 个完整周期，所以这部分的结果就是 (周期乘积)^(floor(n / p^k)) mod p^k。

2. 剩余部分：最后不完整的周期，剩下的 n mod p^k 个数，直接乘进去就行，模p^k。

3. 递归部分：所有原来p的倍数，提出来一个p之后剩下的部分就是 floor(n/p)!，这部分我们可以递归计算。

还是用刚才的例子验证一下： n=10，p=3，k=2，p^k=9：

• 完整周期：floor(10 / 9) = 1个周期，周期内乘积 1×2×4×5×7×8 = 2240 ≡ 2240 - 248×9 = 8 mod 9，所以周期部分是 8^1 mod9 = 8。

• 剩余部分：10 mod9 = 1，也就是剩下1个数10，去掉3的倍数就是10，所以剩余部分乘10，得到 8 × 10 = 80 ≡ 8 mod9。

• 递归部分：floor(10/3)=3，也就是递归算 3!去掉3的因子模9，结果就是 1×2 = 2，乘进去得到 8 × 2 = 16 ≡ 7 mod9。

最终我们得到10!去掉所有3因子模9的结果就是7，和我们手工计算的结果一致：刚才的第一部分就是 1×2×4×5×7×8×10 = 22400 ≡ 7 mod9，完全匹配！

所以我们可以写出递归公式： $$ f(n) = \left( \text{周期乘积} \right)^{\lfloor \frac{n}{p^k} \rfloor} \cdot \text{剩余乘积} \cdot f(\lfloor \frac{n}{p} \rfloor) \pmod{p^k} $$ 边界条件就是f(0)=1，完美！

四、合并结果：中国剩余定理

我们拆分得到了一组同余式 C(n,m) ≡ ai mod mi，其中所有mi两两互质，我们用中国剩余定理合并就能得到最终结果 C(n,m) mod p。

中国剩余定理的合并方法这里就不展开了，简单说就是对于k个同余式，我们可以两两合并，最后得到一个总的同余式，就是我们要的结果。

五、整体算法步骤总结

现在我们把扩展Lucas整个流程整理成清晰的步骤，方便大家记忆：

输入：n, m, p（求 C(n,m) mod p）

1. 分解模数p：把p分解为 p = m1 * m2 * ... * mk，其中 mi = pi^ki，pi是质数，两两互质。

2. 分别计算每个mi：对每个mi=pi^ki：

• 用勒让德公式计算x = n!中pi的幂次 - m!中pi的幂次 - (n-m)!中pi的幂次。

• 用我们上面推导的递归方法，计算 a = f(n) * inv(f(m)) * inv(f(n-m)) mod mi，其中f(n)是n!去掉所有pi因子模mi的结果，inv是模mi下的逆元。

• 如果x >= ki，说明pi^ki能整除整个组合数，所以ai = 0，否则 ai = a * pi^x mod mi。

3. 中国剩余定理合并：把 C ≡ ai mod mi 合并，得到最终结果 C mod p。

六、复杂度分析

整个扩展Lucas的复杂度其实不算高，主要开销来自：

• 分解p的质因数，最多分解到√p，p一般不会超过1e9，所以非常快。

• 计算f(n)的递归深度是log_p n，非常浅，而且周期乘积只需要算一次，实际运行速度很快。 对于常见的编程竞赛题目，n和m到1e18都能处理，完全没问题。

七、常见注意事项

1. 边界处理：C(n, m)当m<0或者m>n的时候，结果一定是0，不要忘了提前判边界，可以省很多时间。

2. 逆元存在性：我们提走所有p因子之后，剩下的部分一定和p^k互质，所以逆元一定存在，不用担心逆元不存在的问题。

3. 递归优化：f(n)可以写成非递归形式，不过递归本身深度很低，写递归更简洁不容易错。

4. 数据范围：当计算幂次的时候，注意x可能很大，只要x >= ki，直接返回0就可以，不需要再计算乘法，避免溢出。

八、总结

扩展Lucas定理本身没有那么难，核心思路就是分解质因数+中国剩余定理合并，难点主要在于怎么处理p^k下组合数计算，通过提走p因子、找周期递归的方法，我们巧妙解决了逆元不存在的问题。

理解了整个推导过程之后，写代码其实就是把我们推导的步骤一步步实现，只要注意边界和溢出，就能得到正确结果。现在你应该彻底搞懂扩展Lucas定理了吧！