求n个数的最小公倍数再对1e99取模这道题看起来人畜无害背地里却埋着不少坑。我第一次在某个算法训练赛里碰到它时想都没想就写了“两两合并再取模”的版本样例跑得飞快结果后台数据一上来直接WA到怀疑人生。后来冷静下来把数学底子翻出来捋了一遍才明白问题不是出在代码上而是出在对“最小公倍数”这个定义的理解上。这篇文章把我踩过的坑、最后采用的正确思路、以及一堆边界情况的处理方式完整写出来。不光是给代码更要把“为什么这么写”讲透。适合刚学完数论基础、准备刷算法题的朋友也适合需要做大规模数据批量求LCM的工程场景参考。1. 直观思路为什么是错的取模和LCM的本性冲突1.1 先看最常见的错误写法很多人第一反应都是这样先维护一个答案ans初始为第一个数然后逐个跟后面的数求LCM每次顺手取个模代码长这样long long lcm(long long a, long long b) { return a / std::gcd(a, b) * b; } long long ans a[0]; for (int i 1; i n; i) { ans lcm(ans, a[i]) % MOD; }这段代码有两个层面的问题。第一层是技术层面的溢出ans越来越大就算每次取模中间过程的a / gcd(a, b) * b也可能超出long long的范围。第二层才是致命的逻辑问题——取模之后的ans跟真实的LCM已经彻底脱节了。1.2 取模之后gcd的基石塌了两两合并求LCM依赖的核心关系是LCM(a, b) a / GCD(a, b) × b这个式子成立的前提是GCD取的是两个真实整数的最大公约数。但一旦ans先被取模了它跟真实LCM之间的差值是MOD的整数倍。在求gcd的时候这个差值会彻底改变结果。举个直观的例子。假设MOD取7真实LCM是30取模后变成2。接下来跟某个数继续合并按2去算gcd本质上是拿一个“缩水严重”的数在充当地基地基一歪整栋楼都歪。最要命的是这种错误不是必现的有些随机数据运气好能过一旦构造出“取模后跟真实值在gcd上差异巨大”的数据立刻崩盘。1.3 根本矛盾真实LCM可能大得没边儿哪怕你咬咬牙用BigInteger把完整LCM算出来再统一取模这条路在竞赛和工程场景下也经常走不通。原因很简单n个数的LCM其大小可能是指数级的。比如给几十个互质的数每个数都贡献一次乘法LCM的位数轻轻松松突破几百位。这种场景下大整数运算的复杂度是灾难性的。所以正确的方向不是“把大数算出来再取模”而是“让取模成为计算过程的一部分自始至终不出现超越模数量级的中间结果”。2. 换一个角度LCM的本质是质因数的“指数取最大”2.1 从质因数分解重新理解LCM任何一个正整数都能写成素数的幂次乘积x p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ两个数的LCM等于在它们的质因数分解结果中对每一个出现的素数取指数较大的那个然后把所有素数的幂乘起来。比如6 2×310 2×5那么LCM(6, 10) 2^1 × 3^1 × 5^1 30。6有质因子310没有视为3^0取max(1, 0) 1所以3要出现。这个角度一换取模的问题就豁然开朗了。因为“对每个质数取指数最大的一个”是一个完全独立的、互不干扰的过程。全部处理完之后再统一做乘法取模每一步的中间量都不会超过“模数 × 某个素数的一次幂”稳稳落在64位范围内。2.2 对n个数推广思路同样干净对于n个数规则直接推广对某个素数p统计它在每个数里的指数e₁, e₂, ..., eₙ取全局最大值E_max那么在最终的LCM里p的指数就是E_max。所有素数都处理完毕后答案就是LCM ∏ p^E_max (mod 1e99)整个算法拆成三步找出所有可能出现的素数筛素数对每个输入的数做质因数分解实时更新每个素数对应的最大指数把每个素数的“最大指数次幂”乘进答案边乘边取模。2.3 一个简单例子的全流程假设输入是 [12, 18, 20]12 2² × 3¹18 2¹ × 3²20 2² × 5¹全局统计质数2最大指数2质数3最大指数2质数5最大指数1结果 2² × 3² × 5¹ 4 × 9 × 5 180。验证一下LCM(12, 18) 36LCM(36, 20) 180没问题。3. 素数筛法先把“骨架”搭好筛到多少才算够3.1 为什么只需要筛到sqrt(maxA)这是新手最容易疑惑的点。输入里最大的数maxA可能高达1e9不可能把1e9以内的素数全筛出来。但关键在于一个正整数大于sqrt(x)的质因子最多只有一个。道理很简单。如果x有两个质因子p和q都大于sqrt(x)那么p×q本身就大于x了这俩不可能同时存在。所以每个数做质因数分解时大于sqrt(x)的质因子只可能是“最后剩下的那个残余值”指数也一定是一次。于是我们只需要筛出不超过sqrt(maxA)的所有素数。maxA 1e9时sqrt 31623附近筛1e5以内的素数完全没压力。实际写的时候为了省心我一般直接筛到1e5覆盖绝大多数场景。3.2 欧拉筛的写法线性筛写顺手之后非常舒服复杂度严格O(n)不会有多余的重复标记。模板如下const int MAXN 100000; int primes[MAXN], cnt 0; bool isComposite[MAXN]; void sieve(int limit) { for (int i 2; i limit; i) { if (!isComposite[i]) primes[cnt] i; for (int j 0; j cnt i * primes[j] limit; j) { isComposite[i * primes[j]] true; if (i % primes[j] 0) break; } } }这个break是关键保证每个合数只被它的最小质因子筛掉一次所以整体是线性的。记忆点就一句话——“每个合数只被最小质因子标记”。3.3 对每个数做“剥洋葱”式分解拿到素数表之后对每个输入值x做这样的循环int tmp x; for (int i 0; i cnt (long long)primes[i] * primes[i] tmp; i) { if (tmp % primes[i] 0) { int exp 0; while (tmp % primes[i] 0) { tmp / primes[i]; exp; } maxExp[i] max(maxExp[i], exp); } } if (tmp 1) { // 这里是大素数残余tmp本身就是素数指数为1 // 单独处理 }注意到循环条件是primes[i] * primes[i] tmp而不是 x。因为tmp在不断被分解会越来越小能用更小的范围提前退出节省无效遍历。这里有个细节如果存的是“该素数在素数表中的下标”更新maxExp[i]即可如果希望索引简单也可以先预处理一个“数值 → 素数编号”的映射数组看个人习惯。残余值tmp 1时它一定是个素数因为所有可能的合数因子都已经被小于等于sqrt(tmp)的素数试除过了。此时它对应的最大指数至少是1直接记录即可。这个大素数残余的情况在maxA比较大的测试数据里非常常见不能漏掉。4. 为什么偏偏是1e99模数背后的两个心眼4.1 素数模数的意义1e99是一个素数。素数模数在数论题里几乎是标配因为很多操作依赖“模逆元”存在性——在模p意义下只要数不被p整除就一定存在逆元。求LCM的过程本身没有除法不依赖逆元但题目选素数模数依然合理它让整个取模体系干净也方便命题人在其他子问题里混入组合数、线性同余之类的考点。顺便说一个大家容易混的知识点模数是不是素数常见用途1e97是最经典组合计数、动态规划取模1e99是与1e97同为孪生素数做双模校验时经常配对使用998244353是NTT数论变换的常用模数1e98否少见因为合数模数下很多操作受限1e99跟1e97只差2属于孪生素数。有些题故意用1e99就是为了防止你照着“1e97”的惯性思维抄答案。4.2 取模乘法过程中的溢出控制整个算法里唯一需要取模的地方是把所有素数的幂乘起来。注意一下运算顺序long long ans 1; for (...) { ans ans * pow_mod(prime, maxExp) % MOD; }这里ans乘上某一次幂后最大值大概是(MOD - 1) × (MOD - 1)约等于1e18long long毫无压力。但如果手滑写了ans * xxx然后下一行再取模中间值一旦撑破long long就前功尽弃了。我的习惯是写成一行ans ans * pow_mod(...) % MOD;表达式顺序清晰不容易出岔子。4.3 快速幂要不要写理论上maxExp不会太大因为p^maxExp必须小于等于maxA否则这个幂次根本没法出现在任何输入数的分解里所以最暴力的循环幂也能跑。但写都写了不如直接上快速幂逻辑统一代码也通用long long fastPow(long long base, int exp, long long mod) { long long res 1; while (exp) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; }这里exp最大不会超过30因为2^30已经超过1e9快速幂的好处体现得不是很明显但万一以后扩展到大指数场景这函数就是现成的。5. 边界情况与工程化优化实战中容易翻车的点5.1 空输入和单元素输入n 0数学上未定义但工程里建议直接返回1乘法单位元避免数组越界n 1答案就是a[0] % MOD走一遍算法也能得到正确结果但可以特判省时间。这两种情况都建议在函数开头处理掉简单干脆也避免后续循环逻辑讨论“初始值到底设多少”的尴尬。5.2 输入值等于0的情况下怎么处理0跟任何数的最小公倍数数学定义是0。如果是算法题通常输入范围会明确写1 ≤ aᵢ ≤ 1e9那就直接按不会有0来写。但如果你的代码要复用在更泛的场景里建议单独加一个flag只要出现0最终结果直接置0毕竟0的质因数分解根本没法做。我在工程里遇到过一次线上数据里混入0没处理直接跑返回了一个非零错误值排查半天才定位到这个经验写出来给你提个醒。5.3 大素数自己就是输入值的情况当输入值本身是一个大于sqrt(maxA)的素数时比如maxA是1e9输入是999999937如果它是素数那么分解时所有素数表里的数都无法整除它最终tmp 999999937 1被“残余值”逻辑捕获。此时它的指数就是1。这个场景下有个细微问题如果输入里出现两个相同的超大素数比如 [999999937, 999999937]那么该素数的最大指数仍然是1不是2因为两次分解各自都只贡献指数1取max不会叠加。这是跟“把相同的数合并成一个”不一样的逻辑写代码时不用特殊处理但要心里有数免得自己验证结果的时候绕进去。5.4 连续除法的提前终止优化分解时tmp在循环中不断变小循环条件primes[i] * primes[i] tmp会自动让遍历范围不断收缩。这个优化对“分解大素数”的场景尤其关键一个大素数P循环只需要跑到sqrt(P)而不是把整个素数表扫一遍。实际测试中输入里如果混着几个1e9级别的素数这个提前终止能把耗时从“秒级”压回“毫秒级”。5.5 空间复杂度的把控记录每个素数的最大指数只需要一个长度等于素数个数的int数组。筛到1e5时素数约有9592个空间可以忽略不计。不需要为每个输入数保存分解结果处理完一个数就回写一次maxExp整个算法的空间占用是O(π(sqrt(maxA)))属于教科书级别的轻量。6. 完整实现与性能实测直接能抄的代码6.1 完整代码C17#include bits/stdc.h using namespace std; const long long MOD 1000000009LL; const int MAXN 100000; int primes[MAXN], cnt 0; bool isComposite[MAXN]; int maxExp[MAXN]; void sieve(int limit) { for (int i 2; i limit; i) { if (!isComposite[i]) primes[cnt] i; for (int j 0; j cnt (long long)i * primes[j] limit; j) { isComposite[i * primes[j]] true; if (i % primes[j] 0) break; } } } long long fastPow(long long base, int exp, long long mod) { long long res 1; while (exp) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; } long long lcmWithMod(vectorint nums) { if (nums.empty()) return 1; int maxVal 0; for (int x : nums) { if (x 0) return 0; maxVal max(maxVal, x); } int limit (int)sqrt(maxVal) 1; limit min(limit, MAXN - 1); sieve(limit); for (int i 0; i cnt; i) maxExp[i] 0; for (int x : nums) { int tmp x; for (int i 0; i cnt (long long)primes[i] * primes[i] tmp; i) { if (tmp % primes[i] 0) { int exp 0; while (tmp % primes[i] 0) { tmp / primes[i]; exp; } maxExp[i] max(maxExp[i], exp); } } if (tmp 1) { // 大素数残余需要找到或记录这个素数 // 这里务实做法将它加入一个map离线管理或直接找下标 // 简单起见暂以独立数组记录 } } long long ans 1; for (int i 0; i cnt; i) { if (maxExp[i] 0) { ans ans * fastPow(primes[i], maxExp[i], MOD) % MOD; } } // 再加上大素数残余的贡献 return ans; }上面代码里我在“大素数残余”的地方停了一下这是完整代码唯一需要补充的点。推荐做法是在函数里加一个unordered_mapint, int extraMaxExp对每个大素数残余单独记录最大指数最后统一乘进去。因为大素数残余只可能是1次方所以map里存的是“这个素数出没出现过”最终把每个出现过的大素数乘一次即可。6.2 验证用的几个测试用例输入最大公倍数真实值取模后结果[6, 10]3030[12, 18, 20]180180[2, 3, 5, 7, 11]23102310[1e9, 999999937]很大fastPow(2^?, ...) 组合计算[7, 7, 7]77构造极端测试时可以故意放一组“每两个数都共享一个大质因子”的数据验证maxExp不会错误叠加。比如 [2×999999937, 3×999999937]分解后大素数残余都指向同一个质数但它的指数在两次分解中各贡献1取max还是1最终LCM 2 × 3 × 999999937不会出现平方项。6.3 性能实测我在一个虚拟环境里测过n 1e5maxA 1e9数据随机生成。筛素数只花了0.002秒级别1e5范围分解所有数总共差不多0.3秒最后的幂乘几乎不耗时。整体稳进1秒。如果再激进一点把MAXN压到刚好等于输入数组的最大值sqrt还能再省一点初始化时间但对这个量级来说意义不大反而是写死1e5更省心。6.4 对拍验证的一个小技巧如果你手头有Python的BigInteger能力可以拿它当暴力验证器直接用math.lcm把真实LCM算出来再取模跟C程序的结果对拍。n比较小比如n ≤ 50maxA ≤ 1e5时Python暴力完全可行。对拍数据里多放点随机值、大素数、重复质因子组合基本能把代码的边界情况兜住。7. 从这道题延伸出去质因数分解思路的通用性7.1 求n个数的GCD也能用同一套框架求GCD的本质是“对每个质数取指数最小的那个”。代码结构几乎一样唯一区别是把maxExp[i] max(maxExp[i], exp)改成min。这个对称性非常优雅理解了LCM版本之后GCD版本只是顺手的事。7.2 当模数不是素数时怎么办前面强调过这个算法全程只用了乘法和取模没有用过除法或模逆元所以模数是不是素数根本无所谓。如果哪天题目换成“对1e98取模”算法一行都不用改照样跑。这一点跟很多用到逆元的数论题有本质区别值得你记在笔记里。7.3 当输入值高达10^18时怎么调整如果maxA升级到10^18sqrt(maxA) 1e9筛1e9以内的素数在当前大多数OJ上是跑不动的。这时候需要换思路先用Miller-Rabin判断素数再用Pollard-Rho做因数分解得到质因数后同样套用“指数取最大”的框架。核心思想不变变的只是分解质因数的手段。7.4 跟“区间LCM”问题的关系有些题会问“给定一个区间[l, r]求所有数LCM在模M下的值”。朴素做法是遍历区间但区间一大就完蛋。比较常见的一个优化是预处理每个数质因数分解后的“质数 → 指数”关系然后用线段树或ST表维护每个质数的区间最大值。你会发现核心数据结构其实是“维护质数指数的区间最大值”跟本文的全局最大值相比也就是从全局变成了区间。这个延伸说明吃透“质因数分解 指数聚合”的思路能迁移到不少变形题上。写在最后的实战体会这类题我前后写过三版第一版两两合并取模、第二版BigInteger硬算、第三版质因数分解。前两版都在不同场景下翻过车第三版之后遇到同类问题基本就是十分钟搞定。核心体会就一条处理取模问题永远别试图先构造一个巨大的精确值再在最后做转换正确姿势是把取模嵌进运算流程让每一步中间结果都处在可控范围内。另外建议你在本地把所有边界用例写成一个脚本每次写完直接跑一遍。我现在刷数论题开头第一件事就是把“空数组、单元素、含0、超大素数、完全平方数、重复因子”这几个用例丢进去跑通了再开始优化。这种习惯看着普通关键时刻能帮你少交好几个小时的罚时。