1. 从题面到关键结论f(i,j) 就是区间 lcm这道题我刚拿到手的时候第一反应是“又要推 lcm 的区间贡献公式”说实话有点头疼。但仔细读完题面发现数据范围藏在背景设定里每个 a_i 都是 Niton 数也就是质因子只可能是 2 和 3。这个限制直接改变了整个题的难度走向。先把题面翻译成人话有一个长度为 n 的数组定义 f(i,j) 表示从区间 i~j 中选出一个非空子序列所有选出来的数的 lcm 的最大值然后求所有满足 ij 的 f(i,j) 之和。这里有个很容易踩的坑f(i,j) 并不是“区间所有数的 lcm”而是“所有子序列 lcm 的最大值”。初看这俩不一样因为如果只选一部分数lcm 可能比全选小。但本题特殊——质因子只有 2 和 3导致所有子序列 lcm 的最大值恰好等于区间内所有数的 lcm。为什么设 a_k 2^{x_k} * 3^{y_k}。任意一个子序列的 lcm它的 2 的指数一定不超过这个区间内所有 x_k 的最大值3 的指数一定不超过所有 y_k 的最大值。而如果我把区间里所有数都选上这两个上界能同时达到。所以最大值就是全选也就是区间 lcm。这个结论是整个做法的地基虽然简单但一定要先想清楚。得到这个结论后题目就变成了求所有子区间 lcm 之和。注意题目要求 ij也就是长度至少为 2 的区间。后面实现时我们一般先算所有长度 ≥1 的区间最后再减去长度为 1 的区间贡献。2. 把 lcm 映射成二维点max 操作是核心既然每个数只含 2 和 3 两种质因子那么每个数 a_i 都能唯一表示成二维坐标 (x_i, y_i)。比如 a_i 12 2^2 * 3^1对应点 (2,1)。一个区间 [l,r] 的 lcm 就对应点( max_{i∈[l,r]} x_i , max_{i∈[l,r]} y_i )也就是说区间 lcm 的质因子指数等于区间内每个质因子指数的最大值。lcm 这个看起来很不“可加”的运算在二维坐标下变成了逐项取 max。这是本题最核心的转化。这时问题变成有 n 个二维点 (x_i, y_i)对每个子区间求区间内点坐标的逐项最大值然后累加 2^X * 3^Y。如果直接枚举所有区间O(n^2) 肯定不行。但 x_i 最大是 30因为 2^30 约 1e9y_i 最大是 18因为 3^18 约 3.8e8坐标范围特别小这个性质要好好利用。我一开始想偏了试图对每个数单独算贡献比如统计每个 (x,y) 出现多少次然后乘上某个权重。测样例发现不对原因是区间 [2,3] 的 lcm 是 6 2^1 * 3^1而这个点 (1,1) 不属于原数组中的任何一个数。也就是说区间 lcm 的二维坐标可能是多个数“互补”出来的不能简单按原始点做贡献拆分。这个坑希望大家不要再踩。3. 从左端点的角度看状态段数为什么有界现在考虑一个固定右端点 r。对于每个左端点 l设 S_l (X_l, Y_l) 是区间 [l,r] 的 lcm 坐标。当 l 从 1 增大到 r 时区间越来越短所以 X_l 单调不增Y_l 也单调不增。也就是说序列 S_1, S_2, ..., S_r 是一个二维单调不增序列。如果我们把连续相同的 S_l 合并成一段那么相邻两段的坐标至少有一个严格变小。因为 X 最多从 30 降到 0Y 最多从 18 降到 0所以两坐标的总变化次数最多 301848 次因此段数最多 49 段。这个上界非常重要是整个算法复杂度的保证。举个例子帮助理解假设固定 r左端点 l 从 r 往左移动每加入一个新数X 和 Y 只会变大或不变。一次“变大”至少消耗 1 的指数增量而 X 总共只能增加 30 次Y 总共只能增加 18 次所以变化次数有限。这不是玄学而是坐标范围给的福利。因此我们可以枚举右端点 r同时维护一个压缩后的状态数组里面存若干段连续的左端点区间每段有相同的 (X,Y)。每次加入新右端点时所有旧段的 (X,Y) 都要和新点的 (x_r, y_r) 取 max然后新增一段长度为 1 的区间再把相邻相同段合并。由于段数最多 49 段整体复杂度 O(n * 49)非常稳。4. 全量更新 合并我的实现思路与代码代码实现我推荐一种最直观的写法不搞复杂的栈内合并顺序直接“全量更新旧段末尾追加新段再合并相邻相同段”。段数很小所以全量更新完全可行逻辑也最不容易错。具体流程如下预处理每个 a_i 的 (x_i, y_i)即分解出 2 的指数和 3 的指数。可以用 while 循环不断除以 2 和 3。枚举右端点 r 从 1 到 n取出当前点 (curx, cury)。遍历当前所有旧段把每段的 (X,Y) 更新为 (max(X, curx), max(Y, cury))。在末尾追加一个新段 (curx, cury, cnt1)表示左端点等于 r 的长度为 1 的区间。从左到右扫描所有段如果相邻两段的 (X,Y) 完全相同则合并成一个段cnt 相加。遍历最终所有段累计答案每段贡献 cnt * 2^X * 3^Y。这里有个细节要注意步骤 2 中所有旧段与新点取 max 后仍然保持从左到右单调不增的性质因为“和固定点取 max”不会破坏单调性。追加的新段在最右端它的坐标一定小于等于左边所有段的坐标因为区间 [r,r] 是当前右端点下最短的区间它的 max 不可能超过包含它的更长区间。所以合并逻辑没问题。我用了 powers 预处理 2^X 和 3^YX 最大 30Y 最大 18所以数组开到 35 和 25 足够。每段 cnt 最大是 n用 long long 更安全。累加答案时每步取模避免溢出。下面给一份完整的 C 代码我比赛时基本是按这个思路写的#include bits/stdc.h using namespace std; using ll long long; const ll MOD 1000000007; // 请根据题目实际模数修改 struct Seg { int x, y; ll cnt; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; vectorll pow2(35, 1), pow3(25, 1); for (int i 1; i 35; i) pow2[i] pow2[i - 1] * 2 % MOD; for (int i 1; i 25; i) pow3[i] pow3[i - 1] * 3 % MOD; vectorpairint, int pts(n 1); ll single_sum 0; for (int i 1; i n; i) { int x 0, y 0, t a[i]; while (t % 2 0) { x; t / 2; } while (t % 3 0) { y; t / 3; } pts[i] {x, y}; single_sum (single_sum pow2[x] * pow3[y]) % MOD; } vectorSeg seg; ll ans 0; for (int r 1; r n; r) { int curx pts[r].first, cury pts[r].second; for (auto s : seg) { s.x max(s.x, curx); s.y max(s.y, cury); } seg.push_back({curx, cury, 1}); vectorSeg merged; for (auto s : seg) { if (!merged.empty() merged.back().x s.x merged.back().y s.y) { merged.back().cnt s.cnt; } else { merged.push_back(s); } } seg move(merged); for (auto s : seg) { ans (ans s.cnt % MOD * pow2[s.x] % MOD * pow3[s.y]) % MOD; } } ans (ans - single_sum MOD) % MOD; cout ans \n; return 0; }验证一下样例n2a[2,3]。预处理得到点 (1,0) 和 (0,1)single_sum 2 3 5。r1cur(1,0)旧段为空追加新段 (1,0,1)合并后只有一段累加 ans 2^1 * 3^0 2。这个 2 对应区间 [1,1]。r2cur(0,1)旧段 (1,0) 更新为 (1,1)追加新段 (0,1,1)合并后两段不相等所以段序列是 [(1,1,1), (0,1,1)]。累加1 * 2^1 * 3^1 6加上 1 * 2^0 * 3^1 3ans 变成 11。对应区间 [1,1]2[1,2]6[2,2]3。最后 ans - single_sum 11 - 5 6正是 f(1,2) lcm(2,3) 6。完全正确。5. 题目要求的 ij为什么最后减单点贡献最稳题目求的是 sum_{i1}^n sum_{ji1}^n f(i,j)也就是只统计长度至少为 2 的区间。上面的代码先算了所有 i≤j 的区间总和然后减去了所有长度为 1 的区间贡献即每个位置的 a_i 本身。这里我提醒一个容易写错的点不要试图在遍历段时“跳过”新追加的那一段因为新段很可能在合并时和前面的段合到一起从而无法分辨哪个左端点对应 lr。所以最简单可靠的方式就是最后统一减掉 Σ a_i。另外减完后要加 MOD 再取模避免负数答案。这个虽然是小细节但真有人因此 WA 过。还有一点是关于 lcm 最大值和子序列的问题。原题说的是“选出非空子序列”由于没有限制子序列长度所以全选区间一定可行且一定是最大。如果某天题目改成“必须选两个不同的数”或“子序列长度恰好为 k”那这个结论就要重新考虑了。读题时一定看清楚。6. 为什么不能直接按数贡献一个必须理解的失败尝试我一开始把问题想简单了每个数 a_i 是 2^{x_i} * 3^{y_i}是不是统计所有区间时只要对每个位置算它对哪些区间的 lcm 有贡献就行了比如经典的“统计区间 gcd”问题就可以对每个位置维护 gcd 变化段。但 gcd 和 lcm 有本质区别gcd 的值随区间扩大而单调不增lcm 的值随区间扩大而单调不减。对于 gcd每个位置作为“新加入元素”时它能改变的状态段数可以用 O(log V) 控制。对于 lcm如果数组里的数包含很多不同质因子每次加入一个新素数都会让 lcm 变化一次线段数可能达到 O(n)。本题之所以能做是因为质因子只有 2 和 3二维状态空间极小。如果还是试图单独统计每个数对区间的“新增贡献”会遇到一个麻烦一个区间的 lcm 可能由多个数组合而成比如 2 和 3 合出 6而 6 这个值不属于任何一个单一原始数。所以你在按 x 贡献或者按 y 贡献时无法直接拆分。从二维点视角看这个问题就很清晰区间 [l,r] 的贡献是 2^{max x} * 3^{max y}这是一个关于 max 的乘积函数不是可加的。所以必须维护所有可能 (X,Y) 的组合状态而不是单个数的贡献。这里我还想多提一句2^X * 3^Y 看起来像两个独立维度的乘积但我们不能把两个维度的贡献拆开分别算比如“所有区间最大 x 的 2 次幂之和”和“所有区间最大 y 的 3 次幂之和”相乘——因为每个区间的最大 x 和最大 y 是同一个区间的两个属性不能解耦。代码里把 (X,Y) 作为一个整体存入段中正是因为这个原因。7. 比赛时的调试心得如何快速验证正确性这类题写完代码后我建议先自己构造几组小数据手算再和程序输出对比。这里分享几个我常用的测试用例。第一组是 n1只有一个数。此时没有任何 ij 的区间答案应该是 0。我们的代码会先算出区间 [1,1] 的贡献 a_1再在最后减去 single_sum a_1得到 0。这个测试能检查减单点逻辑。第二组是 n2a[1,1]。两个数都是 1那么 f(1,2) lcm(1,1) 1答案应该是 1。代码里点坐标都是 (0,0)r1 累加 1r2 更新后段 (0,0,cnt2)累加 2总数 3减去 single_sum2得到 1。第三组是 n3a[2,3,4]。2 对应 (1,0)3 对应 (0,1)4 对应 (2,0)。手动算一下所有长度≥2区间的 lcm区间 [1,2]6[1,3]12[2,3]12总和 30。程序输出应该也是 30。我建议读者在本地跑一下这组数据如果结果不对基本可以确定是合并逻辑或取模问题。另外如果害怕段数上界理解错了可以在代码里加一个统计最大段数的变量跑完随机数据看看是否超过 49。我实测随机生成 2e5 个点最大段数一般只有 8 到 12 左右49 这个上界是非常宽松的。这也说明即使某个角度上数据稍微放宽一点比如 y 指数上限变成 20算法依然没问题。8. 如果质因子不止 2 和 3这个做法还能推广吗我在赛后想了想如果 a_i 的质因子集合变成 {2,3,5}这个做法还能用吗答案是只要质因子种类数还是常数且每个质因子的指数上界都较小就可以继续用同样的思路。把每个数映射成三维向量 (x,y,z)区间 lcm 变成逐维取 max状态段数上界就变成三个指数上界之和大概是 301812≈60 段依然很小。所以代码框架几乎不用改只是每个点的维度增多合并时要比较三个坐标贡献变成 2^X * 3^Y * 5^Z。但如果质因子种类很多比如有 20 个不同质因子状态维度变成 20 维段数上界会很大这个“全量更新所有段”的做法就不可行了。这时候往往需要更复杂的数据结构比如线段树维护 max 矩阵、分治离线或者题目本身 n 会限制得很小。总之这类题第一步永远是数质因子数量再决定算法路线。我这里给一个可能有点用的经验比赛时看到 lcm 区间求和不要先想高级数据结构而是先看值域和质因子限制。如果每个数都能被很少的质因子表示那么 lcm 的变化状态一定不多。本题就是最典型的例子。9. 最终代码需要注意的几个边界细节最后集中说几个写代码时容易出问题的点都是我实际踩过的。第一个是预处理指数时的循环。如果 a_i 1那么 x0y0两个 while 都不会进入。这种情况是合法的不要漏掉。模数比较大时pow2[0] * pow3[0] 1贡献为 1单点贡献也要算进去。第二个是合并段时用一个新 vector 重新构造不要在原 vector 上一边遍历一边删。因为遍历时下标会乱掉而且合并后需要更新 back原地操作容易写错。我上面的代码先用 merged 收集再 swap简单可靠。如果你熟悉双指针也可以但没必要。第三个是答案取模的位置。cnt 最多 2e5pow2[s.x] 和 pow3[s.y] 都是模数范围内的数但乘起来可能超过 long long其实 2e5 * 1e9 * 1e9 2e23远超 long long所以必须在乘法过程中逐次取模。代码里写成 s.cnt % MOD * pow2[s.x] % MOD * pow3[s.y]每次乘完都取模这样安全。第四个是最后 ans - single_sum 后要加 MOD 再取模。因为 ans 和 single_sum 都是在模意义下的直接相减可能是负数。加上 MOD 只会修正一次因为两者都在 [0, MOD) 区间相减后最小是 -(MOD-1)加一次 MOD 足够。第五个是输入量可能比较大用 ios::sync_with_stdio(false) 和 cin.tie(0) 加速。虽然 n2e5 不大但养成习惯没坏处。我把这些细节写这么细是因为比赛时我就曾经因为“先减单点再取模”导致负数输出又因为“乘法顺序不对”导致溢出。最关键的是我一开始错误理解了子序列 lcm 的最大值以为需要排除某些数结果完全跑偏。希望大家看了这篇后不要再走这些弯路。10. 我对这道题的整体评价与实操建议TBOI Round 1 的这道 P15409放在赛题里属于“思路巧妙但不难写”的类型。它的难点不在代码量而在两个思维跳跃第一个跳跃是从“子序列 lcm 最大值”意识到等于“区间 lcm”。这个跳跃依赖对质因子分解后取 max 的深刻理解。第二个跳跃是意识到“所有左端点对应的二维状态段数有界”从而可以用压缩状态暴力扫。如果让我给一个建议就是做题时多注意数据范围里的“隐藏限制”。这题的 a_i ≤ 1e9 看起来很普通但题面明确指出只有 2 和 3 两种质因子。类似的陷阱在不少比赛里都出现过数字很大但质因子种类极少或者所有数都是某个数的幂这些都能把 lcm / gcd 类问题的状态空间压到很小。从代码结构来说这份题解用的“全量更新旧段 末尾追加 合并相邻段”是我认为最适合比赛速写的写法。它不像一些题解里写的那种“从栈顶向前合并”需要仔细维护顺序关系也不容易在合并时丢状态。虽然每个右端点要遍历全部段更新但段数 max 只有 49实测常数可以忽略不计。最后分享一个小技巧任何时候你觉得一个算法要套很重的东西先花几分钟想想状态总数到底有多少。如果状态总数不超过几百或几千那大概率有暴力压缩的办法。这题就是最好的例子。希望这篇题解能帮你彻底搞懂 P15409也能让你在面对其他 lcm 区间求和问题时多一条思路。