卢卡斯定理

Lucas 定理

引入

Lucas 定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解（详见

定义

Lucas 定理内容如下：对于质数 ，有

观察上述表达式，可知 和 一定是小于 的数，可以直接求解， 可以继续用 Lucas 定理求解。这也就要求 的范围不能够太大，一般在 左右。边界条件：当 的时候，返回 。

时间复杂度为 ，其中 为预处理组合数的复杂度， 为单次求组合数的复杂度。

```cpp
long long Lucas(long long n, long long m, long long p) {
  if (m == 0) return 1;
  return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
```

```python
def Lucas(n, m, p):
  if m == 0:
      return 1
  return (C(n % p, m % p, p) * Lucas(n // p, m // p, p)) % p
```

证明

考虑 的取值，注意到 ，分子的质因子分解中 的次数恰好为 ，因此只有当 或 的时候 的质因子分解中含有 ，因此 。进而我们可以得出

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 的结果

考虑二项式 ，那么 就是求其在 次项的取值。使用上述引理，我们可以得到

注意前者只有在 的倍数位置才有取值，而后者最高次项为 ，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 的倍数次项，后者部分取剩余项，即 。

exLucas 定理

Lucas 定理中对于模数 要求必须为素数，那么对于 不是素数的情况，就需要用到 exLucas 定理。

过程

第一部分：中国剩余定理

要求计算二项式系数 ，其中 可能为合数。

考虑利用

根据 唯一分解定理，将 质因数分解：

对于任意 ，有 与 互质，所以可以构造如下 个同余方程：

我们发现，在求出 后，就可以用中国剩余定理求解出 。

第二部分：移除分子分母中的素数

根据同余的定义，，问题转化成，求 （ 为质数）的值。

根据组合数定义 ，。

由于式子是在模 意义下，所以分母要算乘法逆元。

同余方程 （即乘法逆元）有解 的充要条件为 （裴蜀定理），

然而 无法保证有解，发现无法直接求 和 ，

所以将原式转化为：

表示 中包含多少个 因子， 同理。

第三部分：Wilson 定理的推论

问题转化成，求形如：

的值。这时可以利用

解释

一个示例：22! mod 9

先考虑 ，

比如 时：

将其中所有 的倍数提取，得到：

可以看到，式子分为三个整式的乘积：

1. 是 的幂，次数是 ；

2. 是 ，即 ，由于阶乘中仍然可能有 的倍数，考虑递归求解；

3. 是 中与 互质的部分的乘积，具有如下性质：
   ，
   即：（ 是任意正整数）。
   一共循环了 次，暴力求出 ，然后用快速幂求 次幂。
   最后要乘上 ，即 ，显然长度小于 ，暴力乘上去。

上述三部分乘积为 。最终要求的是 。

所以有：

于是：

同样是一个数的阶乘，所以也可以分为上述三个部分，于是可以递归求解。

等式的右边两项不含素数 q。事实上，如果直接把 n 的阶乘中所有 q 的幂都拿出来，等式右边的阶乘也照做，这个等式可以直接写成：

式中的 和 都表示把分子中所有的素数 都拿出来。改写成这样，每一项就完全不含 了。

递归的结果，三个部分中，左边部分随着递归结束而自然消失，中间部分可以利用 Wilson 定理的推论 0，右边部分就是推论 2 中的 。

下面这种写法，拥有单次询问 的时间复杂度。其中 int inverse(int x) 函数返回 在模 意义下的逆元。

若不考虑 excrt 的复杂度，通过预处理 以内的的所有倍数的乘积，可以使时间复杂度优化至单次 。而如果 p 是固定的，我们在一开始就可以对 p 进行分解，并进行预处理，可以达到总复杂度 。

习题

• Luogu3807【模板】卢卡斯定理
• SDOI2010 古代猪文 卢卡斯定理
• Luogu4720【模板】扩展卢卡斯
• Ceizenpok’s formula