1. 从一道经典数论题说起为什么我们需要exLucas如果你在刷算法题或者研究组合数学时遇到过“计算 C(n, m) mod p”的问题并且 p 不是一个质数那么恭喜你你大概率已经掉进了这个经典的坑里。标准的 Lucas 定理要求模数 p 必须是质数它通过将 n 和 m 转化为 p 进制数递归地计算组合数取模效率极高。但现实是骨感的很多题目为了增加难度或者模拟真实场景比如模数可能是多个质数的乘积给出的 p 是一个合数。当 p 10007 时你可以用 Lucas但当 p 10007 * 2 或者 p 1000000007 时Lucas 定理就失效了。这时候exLucas扩展 Lucas 定理就成为了解决问题的关键武器。简单来说exLucas 的核心目标是解决模数为任意正整数尤其是含质数幂的合数时组合数取模的计算问题。它不像 Lucas 定理那样优雅和直接需要更多的数学工具和步骤但理解其原理和实现细节是深入数论和组合数学的必经之路。很多人在学习时只记住了模板代码却不清楚背后的“为什么”导致稍微变形的问题就无从下手。今天我们就来彻底拆解 exLucas不仅告诉你“怎么做”更要讲清楚每一个步骤“为什么这么做”。2. 问题拆解当模数不是质数时我们面临什么要理解 exLucas首先要明白标准组合数取模在模数为合数时为什么行不通。组合数公式为 C(n, m) n! / (m! * (n-m)!)。在模运算中除法并不总是可行的它需要用到“逆元”。而逆元存在的充要条件是除数与模数互质。当模数 p 是质数时根据费马小定理对于任意不被 p 整除的整数 a其逆元 a^{-1} ≡ a^{p-2} (mod p)。因此我们可以轻松计算 n!、m!、(n-m)! 的逆元从而求出 C(n, m) mod p。但是当 p 是合数时问题来了非互质导致逆元不存在在计算 n! 时如果 n! 中包含了与模数 p 不互质的因子比如 p 的质因子那么 n! 在模 p 下就没有乘法逆元。因为逆元要求 gcd(a, p) 1。分母可能为零因子即使分子分母约分后整体可计算但直接对分母取模再求逆元会得到错误结果因为模运算下的除法法则失效了。因此我们不能直接套用“阶乘 - 逆元 - 乘法”的流程。exLucas 的聪明之处在于它没有硬碰硬地去计算整个模 p 下的值而是换了一个思路将模数 p 分解质因数分别求出组合数对每个质数幂取模的结果最后用中国剩余定理CRT合并。注意这里有一个关键前提exLucas 通常要求模数 p 的质因子分解是已知的或者 p 本身不大可以暴力分解。对于极大的、无法分解的合数exLucas 也无能为力但这在算法竞赛和大多数应用中已经足够。3. 核心思路中国剩余定理CRT与质因数分解假设我们将模数 p 分解为质数幂的乘积p p1^k1 * p2^k2 * ... * pt^kt其中 pi 是质数ki 是正整数并且这些质数幂两两互质。根据中国剩余定理如果我们能分别求出组合数 C(n, m) 对每一个 pi^ki 取模的结果记作 ai ≡ C(n, m) (mod pi^ki)那么我们就可以唯一确定一个在模 p 下的解 x ≡ C(n, m) (mod p)。所以exLucas 的核心问题被转化为了一个子问题如何计算 C(n, m) mod p^k其中 p 是质数k 是正整数一旦我们解决了这个子问题对每个质因子幂求解后再用 CRT 合并即可。CRT 的合并公式是标准的 设 M p1^k1 * p2^k2 * ... * pt^kt Mi M / (pi^ki)ti 是 Mi 在模 pi^ki 下的逆元。 则最终解 x ≡ Σ(ai * Mi * ti) (mod M)。接下来的所有难点都集中在了“计算 C(n, m) mod p^k” 上。4. 攻坚子问题C(n, m) mod p^k 的求法这是 exLucas 最核心、最巧妙也最复杂的一步。我们无法直接计算除法因为分母的阶乘可能包含因子 p导致在模 p^k 下没有逆元。解决思路是将阶乘中所有因子 p 提取出来使得剩下的部分与 p 互质从而可以求逆元。4.1 核心引理阶乘的 p 因子剥离我们定义一个新的函数 f(n, p, k)它表示计算 n! 中剔除所有质因子 p 后对 p^k 取模的值。换句话说我们把 n! 写成两部分 n! p^{e(n)} * f(n, p, k) * (一些与 p 互质的数但已被包含在 f 中) 其中 e(n) 是 n! 中质因子 p 的个数。那么组合数可以表示为 C(n, m) n! / (m! * (n-m)!) [p^{e(n)} * f(n, p, k)] / [p^{e(m)} * f(m, p, k) * p^{e(n-m)} * f(n-m, p, k)] p^{[e(n) - e(m) - e(n-m)]} * [f(n, p, k) / (f(m, p, k) * f(n-m, p, k))]现在指数部分 e(n) - e(m) - e(n-m) 是一个非负整数根据组合数的整数性。如果这个指数 k那么 C(n, m) 就包含至少 p^k 这个因子因此 C(n, m) ≡ 0 (mod p^k)。否则指数 e e(n) - e(m) - e(n-m) 在 0 到 k-1 之间。此时式子变成了 C(n, m) ≡ p^{e} * [f(n, p, k) * inv(f(m, p, k), p^k) * inv(f(n-m, p, k), p^k)] (mod p^k)这里的关键在于函数 f(n, p, k) 的计算结果与 p 是互质的因为我们刻意剔除了所有 p 因子。因此f(m, p, k) 和 f(n-m, p, k) 在模 p^k 下存在逆元我们可以用扩展欧几里得算法求出。于是问题进一步转化为两个子任务如何高效计算 e(n)即 n! 中质因子 p 的个数如何高效计算 f(n, p, k)即剔除 p 因子后 n! 对 p^k 取模的值4.2 计算 e(n)勒让德公式计算 n! 中质因子 p 的个数有一个著名的公式——勒让德Legendre公式 e(n) floor(n/p) floor(n/p^2) floor(n/p^3) ... 这个公式的原理是递归计数1到n中至少有1个因子p的数有 floor(n/p) 个这些数中至少有2个因子p的数即 p^2 的倍数有 floor(n/p^2) 个但它们在第一轮已经被计过一次所以需要再加一次以此类推。 计算 e(n) 的复杂度是 O(log_p n)非常高效。4.3 计算 f(n, p, k)递归与周期性的利用计算 f(n, p, k) 是 exLucas 的算法核心也是性能关键。直接暴力从1乘到n并跳过p的倍数复杂度是 O(n)当 n 很大时不可接受。我们需要发现其中的规律。考虑 n! 1 * 2 * 3 * ... * n。 我们可以把这些数按模 p 的余数进行分组所有 p 的倍数p, 2p, 3p, ..., floor(n/p) * p。所有非 p 的倍数。对于第1组p的倍数我们可以提取出一个公因子 p p * 2p * 3p * ... * floor(n/p) * p p^{floor(n/p)} * (1 * 2 * 3 * ... * floor(n/p)) p^{floor(n/p)} * floor(n/p)!看到了吗这里出现了 floor(n/p)!。这启发我们可以递归处理。对于第2组非p的倍数我们需要计算从1到n所有不被p整除的数的乘积对 p^k 取模。当 n 很大时这个乘积也有规律。因为模 p^k 的剩余系中与 p 互质的数构成了一个乘法群。这个乘积具有周期性。具体来说我们定义函数product(n, p, k)计算 1到n 中所有与 p 互质的数的乘积对 p^k 取模。 一个完整的周期是P p^k。在一个周期 [1, p^k] 内与 p 互质的数的乘积对 p^k 取模的结果是一个常数记作pre[p^k]我们可以预处理出来。计算方法是暴力遍历 1 到 p^k累乘其中与 p 互质的数并对 p^k 取模。因为 p^k 通常不会太大否则计算量剧增这个预处理是可行的。那么对于任意的 nproduct(n, p, k)可以快速计算完整的周期数cnt n / p^k最后一个不完整周期的长度rem n % p^k结果 (pre[p^k] ^ cnt) % p^k * product(rem, p, k) % p^k这里pre[p^k] ^ cnt可以用快速幂计算。而product(rem, p, k)因为 rem p^k可以直接用预处理好的前缀积或者再递归/暴力计算一个小范围。现在我们可以给出计算 f(n, p, k) 的递归式了 f(n, p, k) product(n, p, k) * f(floor(n/p), p, k) % p^k这个递归式的理解至关重要product(n, p, k)处理了当前层 n 中所有非 p 倍数的数的乘积。f(floor(n/p), p, k)则递归处理了所有p 的倍数提取出因子 p 后剩下的那个阶乘部分即 floor(n/p)!。递归的边界是当 n 0 时f(0, p, k) 1。4.4 算法流程与时间复杂度综合以上计算 C(n, m) mod p^k 的步骤为如果 m n直接返回 0。计算指数 e e(n) - e(m) - e(n-m)。如果 e k返回 0。分别计算 a f(n, p, k), b f(m, p, k), c f(n-m, p, k)。计算 b 和 c 在模 p^k 下的逆元 inv_b, inv_c扩展欧几里得。计算结果res (a * inv_b % p^k) * inv_c % p^k。最后如果 e 0则res res * pow(p, e, p^k) % p^k。注意这里pow(p, e, p^k)可能会使 p^e 超过 p^k但因为我们是在模 p^k 下计算所以需要取模。计算 f(n, p, k) 的递归深度为 O(log_p n)每层需要计算product函数而product函数利用周期性复杂度约为 O(p^k) 的预处理和 O(log n) 的快速幂。因此总的时间复杂度主要取决于最大的 p^k。这也是 exLucas 的局限性当模数 p 包含的质因子幂 p^k 很大时比如 p^k 接近 10^6预处理pre[p^k]会非常耗时甚至不可行。在算法竞赛中出题人通常会保证 p^k 在一个可接受的范围内例如 p^k 10^6。5. 完整实现与代码细节理解了原理我们来看代码实现。这里以 C 为例展示一个清晰的 exLucas 实现框架。我们会将关键步骤封装成函数。首先我们需要一些基础函数快速幂、扩展欧几里得求逆元、中国剩余定理合并。// 快速幂 (a^b % mod) long long pow_mod(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } // 扩展欧几里得求 ax by gcd(a, b) 的解同时返回 gcd long long exgcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long d exgcd(b, a % b, y, x); y - a / b * x; return d; } // 求 a 在模 mod 下的逆元要求 gcd(a, mod) 1 long long inv(long long a, long long mod) { long long x, y; exgcd(a, mod, x, y); return (x % mod mod) % mod; // 调整为最小正整数 } // 中国剩余定理 (CRT) 合并方程 x ≡ a_i (mod m_i) // 返回方程组在模 M (所有 m_i 的乘积) 下的解 long long crt(const vectorlong long a, const vectorlong long m) { long long M 1, res 0; for (long long mi : m) M * mi; for (int i 0; i a.size(); i) { long long Mi M / m[i]; long long ti inv(Mi, m[i]); // Mi 模 m[i] 的逆元 res (res a[i] * Mi % M * ti % M) % M; } return res; }接下来是 exLucas 的核心部分。我们需要实现计算e(n)和f(n, p, k)的函数。// 计算 n! 中质因子 p 的个数 (Legendres formula) long long legendre(long long n, long long p) { long long cnt 0; while (n) { cnt n / p; n / p; } return cnt; } // 预处理对于给定的 p 和 k计算周期乘积 pre[p^k] // 这里用一个全局的 unordered_map 来缓存避免重复计算 unordered_maplong long, long long pre_cache; long long calc_pre(long long p, long long pk) { if (pre_cache.count(pk)) return pre_cache[pk]; long long res 1; for (long long i 1; i pk; i) { if (i % p ! 0) { res res * i % pk; } } pre_cache[pk] res; return res; } // 计算 product(n, p, k): 1到n中与p互质的数的乘积模 pk long long product(long long n, long long p, long long pk) { if (n 0) return 1; long long res 1; // 完整周期的乘积用快速幂 long long pre calc_pre(p, pk); long long cnt n / pk; res res * pow_mod(pre, cnt, pk) % pk; // 不完整周期的部分 long long rem n % pk; for (long long i 1; i rem; i) { if (i % p ! 0) { res res * i % pk; } } return res; } // 核心函数计算 f(n, p, k) n! 剔除所有p因子后模 pk 的值 long long factorial_mod(long long n, long long p, long long pk) { if (n 0) return 1; // 递归计算: f(n) product(n) * f(n/p) long long res product(n, p, pk); res res * factorial_mod(n / p, p, pk) % pk; return res; } // 计算 C(n, m) mod p^k long long comb_mod_pk(long long n, long long m, long long p, long long k) { if (m n) return 0; long long pk 1; for (int i 0; i k; i) pk * p; // 计算 p^k // 1. 计算指数 e long long e legendre(n, p) - legendre(m, p) - legendre(n - m, p); if (e k) return 0; // 组合数中 p^k 的因子超过 k 个模 pk 为 0 // 2. 计算 f(n), f(m), f(n-m) long long a factorial_mod(n, p, pk); long long b factorial_mod(m, p, pk); long long c factorial_mod(n - m, p, pk); // 3. 计算逆元并相乘 long long res a * inv(b, pk) % pk * inv(c, pk) % pk; // 4. 乘上 p^e if (e 0) { res res * pow_mod(p, e, pk) % pk; } return res; }最后是主函数exlucas负责质因数分解模数 p对每个质因子幂调用comb_mod_pk再用 CRT 合并。// 主函数计算 C(n, m) mod P, P 为任意正整数 long long exlucas(long long n, long long m, long long P) { if (m n) return 0; // 1. 对 P 进行质因数分解 vectorpairlong long, long long factors; // 存储 (质因子p, 幂次k) long long temp P; for (long long i 2; i * i temp; i) { if (temp % i 0) { long long cnt 0; while (temp % i 0) { temp / i; cnt; } factors.emplace_back(i, cnt); } } if (temp 1) { factors.emplace_back(temp, 1); } // 2. 分别计算 C(n, m) mod p_i^{k_i} vectorlong long a, mods; for (auto [p, k] : factors) { long long pk 1; for (int i 0; i k; i) pk * p; long long val comb_mod_pk(n, m, p, k); a.push_back(val); mods.push_back(pk); } // 3. 中国剩余定理合并 if (a.empty()) return 1; // P1 的情况 return crt(a, mods); }6. 实战中的优化与边界处理上面的代码清晰地展示了原理但在实际使用尤其是算法竞赛中还需要考虑一些优化和边界情况。6.1 预处理product函数的优化在product函数中我们每次计算不完整周期rem的部分时都用了 for 循环累乘。当pk很大比如 10^5且n也很大时这个循环可能被调用很多次递归的每一层都可能有一个不完整周期。一个常见的优化是预处理出前缀积数组。我们可以预处理两个数组pre[i]: 表示从 1 到 i 中所有与 p 互质的数的乘积对pk取模的结果。这里 i 最大取到pk。pre_rev[i]: 表示pre[i]的逆元方便后续计算。这样product(n, p, pk)可以更快地计算product(n, p, pk) pow_mod(pre[pk], n/pk, pk) * pre[n % pk] % pk计算factorial_mod时递归的每一层都能 O(1) 得到product值大大提升了效率。预处理pre数组的复杂度是 O(pk)这是以空间换时间。6.2 关于p^k大小的权衡exLucas 的效率瓶颈在于pk p^k的大小。如果题目中模数 P 包含一个像p2, k30即pk2^30≈1e9这样的因子预处理pre数组是完全不可能的连存储都困难。因此exLucas 能处理的问题其模数 P 的每个质因子幂必须在一个合理的范围内。通常竞赛中pk会限制在 10^6 以内这样预处理是可行的。如果遇到pk过大的情况可能需要更高级的数学方法或者题目本身就有特殊性质。6.3 组合数为零的判断在comb_mod_pk中我们通过判断指数e k来确定组合数模p^k是否为零。这是一个非常重要的剪枝。e的计算使用了勒让德公式是 O(log_p n) 的非常快。提前判断为零可以避免后续昂贵的factorial_mod计算。6.4 逆元计算的注意点在计算f(m, p, pk)和f(n-m, p, pk)的逆元时我们使用了扩展欧几里得算法。这里有一个隐含条件f(m, p, pk)必须与pk互质。这正是我们设计f函数的目的——它剔除了所有因子 p所以必然与pk互质因为pk的质因子只有 p。因此逆元一定存在。6.5 代码实现的健壮性大数处理n和m可能很大10^18但pk通常不会太大。在计算product和递归时要注意使用long long并防止中间结果溢出。乘法操作后要及时取模。递归深度factorial_mod的递归深度是log_p n对于p2n10^18深度最多在60左右栈空间是安全的。缓存机制calc_pre函数使用了unordered_map缓存pre[pk]的值。因为同一个pk可能在多次计算comb_mod_pk时被用到例如 CRT 合并前对不同 n,m 的计算缓存可以避免重复计算。注意如果pk值很多这个缓存可能占用较大内存。7. 应用场景与例题分析exLucas 主要应用于需要计算大组合数取模且模数为合数的场景。典型场景一模数固定且已知分解的题目例如题目直接给出P 10007质数用Lucas或P 10007*13合数用exLucas。你需要计算C(n, m) % P。这种情况下你可以预先将 P 分解好然后调用 exLucas。典型场景二模数可能随输入变化有些题目会给出一个合数 P然后进行多次组合数查询。这时可以在程序开始时对 P 进行一次质因数分解并将因子(p, k)存储起来。每次查询时对每个因子幂计算comb_mod_pk再用 CRT 合并。注意预处理pre数组可能需要根据不同的pk进行。一道例题的思考假设题目计算C(10^18, 10^9) mod 1000000000。 首先分解模数1000000000 2^9 * 5^9。 对于p2, k9计算C(10^18, 10^9) mod 512。 对于p5, k9计算C(10^18, 10^9) mod 1953125。 分别调用comb_mod_pk得到两个结果 a1 和 a2。 最后用 CRT 合并方程组 x ≡ a1 (mod 512) x ≡ a2 (mod 1953125) 得到 x ≡ answer (mod 1000000000)。这里pk最大是 1953125预处理pre[1953125]数组是可行的大约需要 8MB 内存存储 long long 数组。但计算量依然很大因为n达到了 10^18递归计算factorial_mod的层数约为log_5(10^18) ≈ 26层每层计算product需要快速幂整体复杂度可以接受但实现时必须注意优化。8. 与普通 Lucas 定理的对比与选择最后我们来明确一下 exLucas 和 Lucas 定理的适用边界避免误用。Lucas 定理条件模数P 必须是质数。做法将 n, m 转化为 P 进制数递归计算。公式C(n, m) ≡ Π C(ni, mi) (mod P)其中 ni, mi 是 n, m 的 P 进制表示下的各位数字。效率极高时间复杂度 O(log_P n)且不需要处理逆元因为 P 是质数可以用费马小定理快速求逆。代码极其简短。exLucas 定理条件模数 P 可以是任意正整数。通常要求其质因子幂p^k不能太大以便预处理。做法分解 P对每个质因子幂单独计算组合数模值再用 CRT 合并。计算单个质因子幂时需要递归提取 p 因子。效率较低时间复杂度取决于最大的p^k和递归深度。涉及预处理、递归、快速幂、CRT 等多个步骤。代码冗长且复杂。选择策略如果题目明确 P 是质数或者你通过判断发现 P 是质数毫不犹豫使用 Lucas 定理。它更快更简单。如果 P 是合数或者题目没有明确但 P 可能不是质数比如 P 是输入的变量那么就需要使用 exLucas。还有一种特殊情况如果 P 虽然是合数但n 和 m 都非常小比如小于 10^6那么直接预处理阶乘和阶乘逆元用公式计算可能比 exLucas 更简单。但 exLucas 的优势在于 n, m 可以非常大10^18只要p^k不大就行。理解 exLucas 的每一步推导不仅能让你在比赛中多一件利器更能加深你对数论中“模运算”、“逆元”、“中国剩余定理”和“递归思想”的理解。它像是一个精致的工具箱将多个基础数论工具组合起来解决了一个初看起来棘手的问题。自己动手实现一遍调试通过并且用一些数据验证后你才会真正体会到这种“分解-攻克-合并”的数学之美。