卢卡斯定理

Published: by Creative Commons Licence

  • Tags:

卢卡斯定理

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

其中:

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

证明:

由于 因此,只有当$n$为$1$或$p$时,上面二项式中有因子$p$。因此可以推出 利用数学归纳法可以容易得到下面的扩展: 之后我们利用这个扩展证明卢卡斯定理。

扩展卢卡斯

卢卡斯定理,必须要求$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} (mod \phantom{1} p_i^{c_i})$后,利用中国余数定理将结果合并,恢复为${m \choose n} (mod \phantom{1} p)$。

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

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

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

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