卢卡斯定理

Published: by Creative Commons Licence

  • Tags:

卢卡斯定理

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

\[{m \choose n}=\prod_{i=0}^{k}{m_i \choose n_i} (mod\phantom{1}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(mod\phantom{1}p)\) 利用数学归纳法可以容易得到下面的扩展: \((1+X)^{p^i}=1+X^{p^i}(mod\phantom{1}p)\) 之后我们利用这个扩展证明卢卡斯定理。

\[\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 (mod \phantom{1} 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 \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)!$则类似。

\[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!)(mod\phantom{1}p_i^{c_i})\]

其中$(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})$,那么可以推出

\[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 (mod\phantom{1}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}(mod \phantom{1} p)$的时间复杂度为$O(p)$