1. 题目拆解别被“取模”带偏了节奏看到“求n个数的LCM最小公倍数并对1e99取模”这个标题很多人的第一反应是“这有什么难的先求LCM再取模不就行了”。但真上手写代码的时候才会发现这个题的核心难点恰恰不在“求LCM”本身而在于你怎么在求的过程中不爆数据范围以及处理“先算后模”和“边算边模”之间的差异。这道题比较适合两类人一类是刚接触算法竞赛、准备打基础的新手另一类是工作中需要处理大数运算、但对数论不太熟的开发者。从知识点角度看它同时考察了质因数分解、筛法、快速幂、取模运算性质虽然每一块单独拿出来都不难但合在一起就容易出问题。我在实际带人和自己刷题的过程中见过至少有三种不同的错误解法而且每种错误的“死法”还都不一样。先说结论这个题的思路其实很清晰——先把每个数做质因数分解统计每个质因子在所有数字中出现的最大次数然后把这些质因子的最大次数乘起来最后对1e99取模。听上去很简单但每一步都有值得细抠的细节下面我按自己的实战经验把整个推导和实现过程完整拆一遍。1.1 这个题到底在问什么题目本身描述很简单输入n个正整数求出它们的最小公倍数结果对1000000009取模输出。比如输入 2、3、4最小公倍数是12输出12输入4、6最小公倍数是12输出12输入6、8、14最小公倍数是168输出168。但这里有个关键的前提必须想清楚题目没有说这些数的大小范围。在实际的机试和在线评测环境中这类题的常规数据范围通常是 (1 \leq n \leq 10^5)每个数 (a_i \leq 10^9) 甚至更大。如果直接套用“两两求gcd再乘”的公式[ LCM(a,b) \frac{a \times b}{GCD(a,b)} ]一旦数字拉满比如两个数都是 (10^9) 级别那么 (a \times b) 轻松达到 (10^{18})在C的long long里勉强能装下但如果n增加到几十个、上百个数中间结果会迅速膨胀到连__int128都扛不住的地步。更麻烦的是你还需要对结果取模又不能像求“乘积模”那样中途随便取模因为LCM的整除关系和取模运算之间并不完全兼容。这一点下面我会重点展开。1.2 直接求LCM的老路数死在哪先说一种最常见的错误尝试定义一个变量lcm 1然后循环对每个数执行lcm lcm / gcd(lcm, a[i]) * a[i]因为两个数的LCM乘以两个数的GCD等于这两个数的乘积所以这个“先除后乘”的顺序能在一定程度上防止中间结果爆炸同时保证每一步得到的结果都是当前已处理数字的最小公倍数。这个方案在小数据量、小数值范围下完全没问题。但放到这个题里就不行了原因有好几层第一就算你用了“先除后乘”lcm / gcd(lcm, a[i])这一步之后再乘上a[i]也可能非常大。举个例子假设你处理到某一时刻lcm已经包含了若干个不同质因子的高次幂数值可能达到 (10^{17}) 甚至更多再乘一个 (10^9) 级别的数直接溢出。第二你可以设计一个很长的模运算版公式lcm (lcm / gcd(lcm, a[i])) % MOD * (a[i] % MOD) % MOD。看起来每一步都取模了但不要忘记gcd(lcm, a[i])这个运算需要的是真真实实的lcm而你在循环中保存的lcm已经是模意义下的余数了。一个已经被模过的余数再去参与gcd运算得到的根本不是原数之间的gcd那整个LCM计算过程就直接废掉了。第三如果非要在真整数上做只到最后才取模那么中间一旦溢出后面所有的计算都会基于一个错误的结果最后的取模自然也没有意义。所以说对于这个题“两两LCM滚动”这个思路在数学上正确在计算上不可行。我们需要换一个维度去理解LCM这个维度就是质因数分解。1.3 质因数分解视角下的LCM如果我问你12和18的最小公倍数为什么是36你可能脱口而出12的质因子是 (2^2 \times 3)18的质因子是 (2 \times 3^2)把每种质因子的最高次数拿出来就是 (2^2 \times 3^2 36)。这正是问题的本质LCM不关心数字本身长什么样它关心的是每个质因子的最大次数。如果你能拿到每个数字的质因数分解那么所有数字的LCM就是每个质因子的“最大指数”的乘积。这个思路有两个明显的好处。好处一是中间过程不会溢出因为我们不是在累乘一个不断膨胀的整数而只是在统计指数。比如一个数 (10^9)分解后无非就是有限的几个质因子每个质因子的指数都不会很大20以内基本是天花板了因为 (2^{30} 10^9)实际上 (2^{30}) 就已经超过10亿了。好处二是取模变得非常干净——只要在最后乘法和快速幂的时候取模就行因为每次乘的都是 (p^k \bmod MOD)不存在“整个LCM先算出来再模”的溢出问题。可以说拿到这个题第一步就应该是往质因数分解的方向想而不是在“两两合并”这条老路上死磕。2. 核心思路落地质因数分解、指数统计、快速幂思路理清了接下来就是具体怎么落地。这一步里有三个技术细节筛出需要的质数表、分解每个输入数字并更新指数数组、最后用快速幂把答案算出来。分开说。2.1 筛质数的范围怎么定要做质因数分解首先得有质数表。但问题是我需要筛多大的范围假设题目给出的每个数 (a_i) 的范围是 (1 \leq a_i \leq 10^9)那么一个数分解质因数时最多只需要试除到 (\sqrt{a_i}) 就足够了。因为如果一个数在 (\sqrt{a_i}) 之后还有大于 (\sqrt{a_i}) 的因子那么它一定只能是自己本身也就是说这个数本身是一个大质数。所以理论上质数表只要筛到 (\sqrt{10^9}) 也就是31623就差不多了。为了保险我习惯直接筛到45000也就是记录maxNum 45000。为什么选45000因为 (\sqrt{2.1 \times 10^9} \approx 45826)而2的31次方约等于21.47亿只要输入范围在int能表示的范围内45000这个上界基本是够用的。如果题目明确说数字最大到 (10^{12})那筛的上界就要到 (10^6)。说这个是想提醒你筛质数的上限不应该是拍脑袋定的而要根据输入数据范围反推。这一点在写模板题时经常被忽略等出了TLE超时或者漏解的时候才反应过来。筛质数本身用最朴素的埃氏筛就够了在45000的范围内复杂度完全可以接受。我自己的习惯写法是const int MAXV 45000; vectorint primes; bool isComp[MAXV 5]; void sieve() { for (int i 2; i MAXV; i) { if (!isComp[i]) { primes.push_back(i); if ((long long)i * i MAXV) { for (int j i * i; j MAXV; j i) isComp[j] true; } } } }有人可能会问为什么不用欧拉筛线性筛在45000这个规模下埃氏筛和欧拉筛的耗时差别几乎可以忽略不计埃氏筛写起来简单、不容易写错所以我个人更推荐在比赛和刷题时优先用逻辑简单的写法而不是一味追求复杂度上的最优。等你的数据范围真的到了百万级、千万级再换线性筛也不迟。2.2 分解每个数并维护最大指数拿到质数表之后接下来就是核心循环对每个输入的数字x从小到大遍历质数表尝试用每个质数去整除它。这里有一个特别关键的注意点如果x能被某个质数p整除那么要用一个while循环把这个因子尽可能多地剥出来。比如数字12遇到2的时候要一次性数清楚它到底有几个2因子即 (12 2^2 \times 3)2的指数是2而不是1。剥完所有2因子之后x变成3然后再继续用下一个质数去试。伪代码如下int mx[MAXV 5]; // 记录每个质因子的最大指数MAXV要开到数字可能的值域 for (int i 0; i n; i) { long long x; cin x; for (int p : primes) { if ((long long)p * p x) break; if (x % p 0) { int cnt 0; while (x % p 0) { x / p; cnt; } mx[p] max(mx[p], cnt); } } if (x 1) { // 此时x是一个大于sqrt(原x)的质因子指数一定是1 // 但注意x本身可能超过MAXV需要单独处理 } }上面代码里最后一段“x 1”的处理是很多新手容易漏掉的地方。当一个数字的质因子被剥完一轮之后剩下的那个x要么是1要么是一个大于当前试除上限的质数。比如一个数本身是999999937一个很大的质数它不可能被45000以内的任何质数整除最后剩下的x就是这个数本身。这种情况下它的指数是1所以也需要更新mx[x]。但这里就有个问题如果x很大比如是 (10^9) 级别你还能直接开一个长度为 (10^95) 的数组吗显然不行内存直接就爆了。这时候就需要一个哈希表或者用map来记录大质数的最大指数。在C里我喜欢用一个unordered_mapint, int来处理超过数组范围的那部分质因子只有在用数组和用map都能正确表达时才可以选择数组方案。顺带说一句如果一个数的质因子全部被处理完最后剩下的x可能是个1也可能是很多个质数吗不可能因为一个数最多只能有一个大于其平方根的质因子如果它还有两个这样的质因子那这两个的乘积一定大于这个数本身矛盾。这个性质很重要它保证了“如果x 1那么x本身就是一个质数且指数恰好为1”这个结论的成立。2.3 最后一步快速幂把所有因子乘起来统计完所有质因子的最大指数之后答案其实就已经出来了对每个质因子p若它的最大指数是e那么它对最终答案的贡献是 (p^e)把所有贡献乘起来再对MOD取模就是最终结果。这里用到的就是快速幂也叫二分幂。它的原理是把指数拆成二进制然后通过反复平方来减少乘法次数。拿 (2^{10}) 举例10的二进制是1010所以 (2^{10} 2^8 \times 2^2)只需要做几次乘法就够了而不是老老实实地乘10次。快速幂的模板很固定我直接写出来const long long MOD 1000000009LL; long long fastPow(long long base, long long exp) { long long res 1; while (exp 0) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; }为什么要用快速幂直接写一个for循环从1乘到e不行吗表面上看起来可以因为e不会太大撑死了也就30左右。但架不住质因子数量多——如果有几百个质因子每个都循环到30次也就是几千次运算性能上其实也还好。真正的问题是快速幂能让你养成一种“凡事取模、用最优方式处理大数幂次”的习惯在数据范围升级到这个题目的加强版时你不需要再回头改代码。实际统计阶段我会用一个mapint, int maxExp来保存最大指数然后统一遍历它计算答案。这样做的好处是不关心质因子到底是小质数还是大质数也不用为了大质数分配一个巨大的数组代码逻辑统一了很多。3. 实操过程与完整代码实现说了这么多不如直接上一份完整的、可提交的实现。下面这份代码是我在本地测试过的用C17编译能正确处理 (n) 个数、每个数在int范围内的情况。3.1 完整参考代码#include bits/stdc.h using namespace std; const long long MOD 1000000009LL; const int MAXN 45000; vectorint primes; bool isComp[MAXN 5]; void sieve() { for (int i 2; i MAXN; i) { if (!isComp[i]) { primes.push_back(i); if ((long long)i * i MAXN) { for (int j i * i; j MAXN; j i) { isComp[j] true; } } } } } long long fastPow(long long base, long long exp) { long long res 1; while (exp 0) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); sieve(); int n; cin n; mapint, int maxExp; for (int i 0; i n; i) { long long x; cin x; for (int p : primes) { if ((long long)p * p x) break; if (x % p 0) { int cnt 0; while (x % p 0) { x / p; cnt; } maxExp[p] max(maxExp[p], cnt); } } if (x 1) { // 剩余的x本身是一个大质数指数为1 maxExp[x] max(maxExp[x], 1); } } long long ans 1; for (auto kv : maxExp) { int p kv.first; int e kv.second; ans ans * fastPow(p, e) % MOD; } cout ans \n; return 0; }这份代码把“筛质数”“分解统计”“快速幂计算答案”三个步骤拆得很清晰。实际提交的时候你甚至可以只用map而不去管数组下标的问题这也省去了一堆边界判断。3.2 代码里的关键细节逐个说第一个细节if ((long long)p * p x) break;。这一行是整个分解过程能跑得快的前提。因为我们在试除的过程中x是不断变小的一旦当前质数p的平方大于剩余x说明以后不可能再有任何大于p的质因子了直接跳出循环。这个剪枝能让循环提前结束对于本身已经半路被除到很小的数字来说性能提升非常明显。第二个细节maxExp[p] max(maxExp[p], cnt);。注意这里是在更新最大值而不是累加。因为LCM关心的是“每个质因子的最高次数”不是“总次数”。如果把这里写成答案会莫名其妙变成指数的总和那结果就完全不对了。第三个细节maxExp[x] max(maxExp[x], 1);。这一步处理的是大质数的情况。有的同学可能会问那我能不能不判断x 1而是把所有质数表全部试完不能。因为大质数可能比质数表的上限还大你根本试不到它。必须等到循环结束后如果剩下的x不是1就把它单独记录为指数1的质因子。第四个细节mapint, int的键可能很大用int装得下吗输入如果是int范围内的数比如 (2^{31}-1) 级别约21.47亿是小于int正上限的所以int能装下。但保险起见我建议读入用long long参与判断时也转成long long避免乘法溢出。比如p * p这一步如果不加(long long)45000的平方是20.25亿在int的范围边缘万一某次数据范围稍大就会直接溢出成负数导致循环条件错乱。3.3 一个手工推演的例子拿输入[12, 18, 20]来手算一遍加深印象。12分解(12 2^2 \times 3^1)所以暂存maxExp[2] 2maxExp[3] 1。18分解(18 2^1 \times 3^2)此时maxExp[2] max(2, 1) 2maxExp[3] max(1, 2) 2。20分解(20 2^2 \times 5^1)此时maxExp[2] max(2, 2) 2maxExp[5] 1。最终质因子统计结果是2的指数23的指数25的指数1。答案就是 (2^2 \times 3^2 \times 5^1 4 \times 9 \times 5 180)。而12、18、20的最小公倍数确实就是180。这个例子同时验证了不是把所有的指数全部相加否则2的指数会变成5也不只是记录第一次碰到的数而是要取所有数在该质因子上的最大次数。4. 为什么1e99在这里不是“普通”的模数标题里明确给出了模数1e99这不是个随随便便的数。1e99等于1000000009它是一个质数。和更常见的1e97一样这类大质数模数经常出现在组合数、快速幂、逆元等场景中。但在这个题里我们要特别小心一个问题取模运算不保持整除信息。这句话怎么理解我举一个简单的例子。假设MOD 7数字a 4b 6真实LCM是12那么 (12 \bmod 7 5)。但是直接算 (4 \bmod 7 4)(6 \bmod 7 6)然后 (4 \times 6 \bmod 7 24 \bmod 7 3)。可以看到(3) 和 (5) 并不相等。这就说明如果你在求LCM的过程中每一步都天真地对当前结果取模最后得到的东西并不是真实LCM对MOD取模的结果。那为什么在“连续乘一个数再取模”时每一步取模没问题在“求LCM”时就不行了因为连续乘法的每一步之间是纯粹的乘法关系取模可以“穿透”乘号但如果中间夹着一个gcd取模就不能随便穿透了。gcd需要的是完整精确的整数信息任何一个已经模过的余数都会让gcd的结果改变。所以在这个题里我们选择“先统计质因子的最大指数再统一用快速幂乘出来”的方式本质上就是把“取模”推迟到了所有整数精确信息都已经统计完毕之后。这样既避开了大整数溢出又保证了取模的正确性。4.1 一个更贴近题目的验证假设输入[1000000000, 999999937]前者是 (10^9 2^9 \times 5^9)后者是一个质数在本题数据范围内大概率是质数。那么真实LCM就是 (2^9 \times 5^9 \times 999999937)这是一个非常大的数字直接算肯定会超过long long的表示范围。而我们的算法只需要分别记录三个质因子的最高指数然后分别乘到答案里取模即可中间每一步都只有模运算不会溢出。这也说明了为什么这类题目的运行速度往往很快虽然看起来要对n个数逐个分解但每个数被质数试除的次数远远小于质数表的总长度因为一旦剩余部分变成质数或1就会提前跳出循环。4.2 需要考虑逆元吗有些读者可能看到“模数是质数”就条件反射地想到费马小定理和逆元想到是不是要求某个数的逆元来避免除法。这个题里完全不需要。逆元主要是处理“在模意义下做除法”的问题而我们的算法全程都没有除法除了分解过程中对整数本身的除法这个除法是在取模前的整数域上进行的和模逆元完全是两个概念。换句话说模数是质数在这里只是个背景板你把它换成任何一个满足数据范围要求的模数算法结构都不用改。唯一要注意的是快速幂里乘法不能爆long long。由于MOD是 (10^99)两个小于MOD的数相乘最大约为 (10^{18})在Clong long上限约 (9.2 \times 10^{18})范围内是安全的。如果你的模数改成 (10^{18}) 级别那乘法的中间结果就可能溢出到时候还得上“快速乘”或者用__int128。这是后话但提前知道坑在哪里总是好的。4.3 数据范围与复杂度分析筛质数上限45000复杂度 (O(MAXV \log\log MAXV))可以忽略不计。分解阶段每个数需要遍历质数表但因为有平方剪枝真正试除的次数平均远小于质数的数量。在最坏情况下每个数都要遍历约4500个质数n为 (10^5) 时最坏约4.5亿次循环看上去有点吓人但实际上很多数会在前几个质数之后迅速变小加上数学题输入通常不会构造所有数都是大质数相乘的极端情况一般在时限内能跑过。如果你还是不放心可以先用一个unordered_set对输入做去重因为重复数字的分解结果完全一样用一个样例代表就够了。统计答案阶段遍历所有出现的质因子每个做一次快速幂复杂度约 (O(m \log e))。m是不同质因子数量撑死了几千个完全没有压力。总体来看这个算法的时间瓶颈只在分解阶段。实际做题时如果发现TLE优先优化分解阶段的剪枝逻辑而不是去换什么更高级的数学工具。5. 常见问题与现场排查实录作为刷题老手我在这个题上踩过不少坑也给不少朋友和同学做过复盘。下面这些“事故现场”都是真实发生过的我把高频问题和排错思路整理成速查表方便你以后直接避开。5.1 分解“不干净”答案偏小这个问题是我遇到最多的一种。症状是自己拿小数据测试都对一提交就是答案错误而且错的那一组往往包含比较大的质数。原因在于分解循环结束后没有处理剩余的x 1。比如输入一个数字999999937它是一个质数试除到p * p x的时候就退出了循环此时x还是999999937。如果代码里没有最后那个if (x 1)的记录那么这个大质数就彻底被漏掉答案变成了其他小质因子的乘积自然就偏小了。排查的方法很简单在本地造一个[2, 999999937]的输入正确答案应该是1999999874如果跑出来的结果只等于2那基本就是漏了x 1的处理。5.2 大质数的map用错类型另一个常见问题是在记录大质因子时直接写maxExp[x]或者maxExp[x] max(maxExp[x], 1)时如果x是long long类型而mapint, int的键是int编译虽然会通过但会有一个隐式类型转换。更麻烦的是如果某一天输入超过了int范围这个转换会截断产生一个完全错误的键。我在C11之后就养成了maplong long, int的习惯反正现代评测机的内存都不紧张用8字节的键并不会带来什么性能损失。如果实在想省内存也可以把大质数单独存到一个vector里去重最后单独计算但代码就没那么通用了。5.3 快速幂里base平方时溢出这其实是一个隐蔽的坑。表面上看MOD 1e99base在取模后肯定小于MOD那base * base约等于 (10^{18})在long long范围内不会溢出。但如果你的base是int类型那麻烦就来了两个int相乘会先按int计算再赋值给long long中间的溢出发生在int的阶段结果早就是负数了。正确做法是确保fastPow里的base是long long或者在乘法前强转(long long)base * base。同样的道理也适用于上面的p * p x判断。凡是涉及两个int相乘的地方只要乘积可能超过int上限就必须先转型。5.4 模数写错白交几发1e99和1e97这两个数长得很像在实际比赛中我见过有人把模数写成1000000007提交了两次都因为答案错误被罚时。这个问题非常低级但就是会反复发生。我的建议是遇到取模题目第一步不是写代码而是把模数用注释写死在代码最开头// MOD 1000000009 const long long MOD 1000000009LL;这样既清楚又不容易手误。另外注意1000000009后面要加LL后缀否则它默认是int类型在某些平台上可能导致常量溢出警告虽然不一定报错但隐患确实存在。5.5 输入含有相同数字时的冗余计算这个不算坑算优化点。假设输入是一万个重复的数字比如全部都是2000那么你实际上只需要分解一次2000就够了剩下9999次都是重复劳动。处理方式有两种一种是在读入时把数字放进unordered_set去重之后只对去重后的集合进行分解另一种是统计每个数字出现的次数反正最后都是取最大指数分解一遍和分解一万遍效果完全一样。去重后的代码在极端数据下能快几十倍值得养成这个习惯。6. 一点个人经验最后说说我做这道题的一些心得。以前我刚接触数论题的时候也有一个特别不好的习惯拿到题就直接套模板求gcd还是求LCM先写个公式再说。但这类题真正教给我的不是公式而是“在计算之前先想清楚哪些信息可以丢失、哪些信息必须保留”这个思维习惯。整数分解本质上是把大整数转换成一堆不会溢出的“指数信息”然后让取模运算安全地发生在最后。这种从问题本质入手的思路远比死记任何一个题目模板都重要。另外在实现层面我强烈建议你先把分解、统计、幂乘三个步骤分开写函数而不是全部揉在main里。分开写的好处是定位bug的边界更清晰——答案不对的时候先单测分解部分再单测幂乘部分很快就能定位到问题出在哪一环。别急着炫技把代码写得稳妥、直白才是刷题最实用的策略。如果你后面想把这个题再往下扩展可以试试这些变体如果数字范围提升到 (10^{18})单纯的试除法就不够用了需要用米勒-拉宾素性检测配合Pollard-Rho大数分解如果模数不是质数快速幂依然能用但你对“乘法结果不溢出”的前提要更加小心。每扩展一步你都能更深刻地理解这个题当初选1e99的用意。