卢卡斯定理

Published: July 21, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 卢卡斯定理
• 扩展卢卡斯

卢卡斯定理

卢卡斯定理：对于非负整数$m$和$n$和素数$p$，下面同余式成立：

$${m \choose n}=\prod_{i=0}^{k}{m_i \choose n_i} \pmod p$$

其中：

$$m=\sum_{i=0}^{k}m_ip^i\\ n=\sum_{i=0}^{k}n_ip^i$$

满足$0\leq m_i<p$且$0\leq n_i<p$。

证明：

由于 ${p \choose n}=\frac{p(p-1)\ldots(p-n+1)}{n(n-1)\ldots1)}$ 因此，只有当$n$为$1$或$p$时，上面二项式中有因子$p$。因此可以推出 $(1+X)^p=1+X^p\pmod p$ 利用数学归纳法可以容易得到下面的扩展： $(1+X)^{p^i}=1+X^{p^i}\pmod p$ 之后我们利用这个扩展证明卢卡斯定理。

$$\begin{aligned} \sum_{n=0}^m{m \choose n}X^n&=(1+X)^m\\ &=(1+X)^{\sum_{i=0}^km_ip^i}\\ &=\prod_{i=0}^k((1+X)^{p^i})^{m_i}\\ &=\prod_{i=0}^k(1+X^{p^i})^{m_i}\\ &=\prod_{i=0}^k\sum_{n_i=0}^{m_i}{m_i \choose n_i}X^{n_ip^i}\\ &=\prod_{i=0}^k\sum_{n_i=0}^{p-1}{m_i \choose n_i}X^{n_ip^i}\\ &=\sum_{n=0}^m(\prod_{i=0}^k{m_i \choose n_i})X^n \pmod p \end{aligned}$$

扩展卢卡斯

卢卡斯定理，必须要求$p$为素数，这是一个非常严苛的要求。即使$p$不是素数，我们实际还是可以用卢卡斯定理进行加速。

首先由算术基本定理可知$p=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}$，其中$p_i$为互不相同的素数，$c_i\geq 1$。之后我们需要计算出所有的${m \choose n} \pmod p_i^{c_i}$后，利用中国余数定理将结果合并，恢复为${m \choose n} \pmod p$。

但是我们还需要解决一个问题，怎么计算${m \choose n} \pmod{p_i^{c_i}}$呢。如果$c_i$为$1$，那么实际上直接就可以使用卢卡斯定理，但是如果$c_i$不是$1$，我们必须采用其它方法。

$${m \choose n}=\frac{m!}{n!(m-n)!}=\frac{\frac{m!}{p_i^{a}}}{\frac{n!}{p_i^b}\cdot\frac{(m-n)!}{p_i^{c}}}\cdot{p_i^{a-b-c}}$$

我们需要做的是从$m!$中提取所有的因子$p_i$并算出其余的阶乘值。而$n!$和$(m-n)!$则类似。

$$\begin{aligned} m!&=1\cdot2\cdots m\\ &=(1\cdot2\cdots (p_i-1)\cdot 1\cdot(p_i+1)\cdots m)(p_i\cdot2p_i\cdots \lfloor \frac{m}{p_i}\rfloor p_i)\\ &=p_i^{\lfloor \frac{m}{p_i}\rfloor}(1\cdot2\cdots (p_i-1)\cdot 1\cdot(p_i+1)\cdots m)(1\cdot2\cdots \lfloor \frac{m}{p_i}\rfloor)\\ &=p_i^{\lfloor \frac{m}{p_i}\rfloor}(1\cdot2\cdots (p_i-1)\cdot 1\cdot(p_i+1)\cdots m)(\lfloor \frac{m}{p_i}\rfloor!)\pmod{p_i^{c_i}} \end{aligned}$$

其中$(1\cdot2\cdots (p_i-1)\cdot 1\cdot(p_i+1)\cdots m)$是周期为$p_i^{c_i}$的序列。我们可以记这样的序列为$G(m)$，而记$F(m)=m!\pmod{p_i^{c_i}}$，那么可以推出

$$F(m)=p_i^{\lfloor \frac{m}{p_i}\rfloor}G(m)F(\lfloor\frac{m}{p_i}\rfloor)\\ =p_i^{\lfloor \frac{m}{p_i}\rfloor}G(p_i^{c_i})^{\lfloor\frac{m}{p_i^{c_i}}\rfloor}G(m\pmod{p_i^{c_i}})F(\lfloor\frac{m}{p_i}\rfloor)$$

如果我们能预先计算出所有的$G(1),G(2),\ldots ,G(p_i^{c_i})$，那么计算$F(m)$的时间复杂度将为$O(p_i^{c_i}+(\log_2m)^2)$。而计算${m \choose n}\pmod p$的时间复杂度为$O(p)$