卢卡斯定理

引入

本文讨论大组合数取模的求解。组合数，又称二项式系数，指表达式：

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} .

规模不大时，组合数可以通过递推公式求解，时间复杂度为 $O (n k)$ ；也可以在较大的素数模数 $p > n$ 下，通过计算分子和分母的阶乘在 $O (n)$ 时间内求解。但当问题规模很大（ $n \sim 10^{18}$ ）时，这些方法不再适用。

基于 Lucas 定理及其推广，本文讨论一种可以在模数不太大 ( $m \sim 10^{6}$ ) 时求解组合数的方法。更准确地说，只要模数的唯一分解 $m = \prod p_{i}^{e_{i}}$ 中所有素数幂的和（即 $\sum p_{i}^{e_{i}}$ ）在 $10^{6}$ 规模时就可以使用该方法，因为算法的预处理大致相当于这一规模。

Lucas 定理

首先讨论模数为素数 $p$ 的情形。此时，有 Lucas 定理：

Lucas 定理

对于素数 $p$ ，有

(\binom{n}{k}) \equiv (\binom{⌊ n / p ⌋}{⌊ k / p ⌋}) (\binom{n mod p}{k mod p}) (\mod p) .

其中，当 $n

本页面最近更新：2025/8/24 15:29:16，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, c-forrest, GitPinkRabbit, Great-designer, TonyYin0418, Xeonacid, EntropyIncreaser, ksyx, MegaOwIer, sshwy, Henry-ZHR, iamtwz, ouuan, Sheng-Horizon, CornWorld, IceySakura, Ir1d, LuoYisu, Marcythm, megakite, Menci, shawlleyw, StudyingFather, Tiphereth-A, whongzhong, YOYO-UIAT
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用