凌晨两点的笔试群里已经炸了。2026年携程暑期实习3月29日这一场开发岗和算法岗共用这套题前几题大家还能边聊天边写到了第四题群里突然安静了十几分钟然后开始有人问“min和gcd这题到底要干什么”。我自己的状态也好不到哪去盯着题目看了五分钟第一反应是“这不就是数论题吗”结果写着写着才发现这题真正考的不是数论而是“你怎么把 O(n²) 的子数组问题压到 O(n log n)”核心是 min 的单调栈 gcd 的分段势能。这篇文章就是我的完整复盘题目、思路、Java/C/Python 三种实现以及我踩过的坑全部写出来。先说结论这道题如果你只背过 Java 面试八股文或者只刷过 C 基础语法和 Python 入门大概率会在暴力循环里卡死。它不是那种“会一个算法模板就能过”的题而是需要你现场把 min 和 gcd 两个不相关的性质组合起来。这种题在笔试里属于典型的“第四题分水岭”前 60 到 80 分钟你还在做前三题第四题开始就要拼真实的算法功底了。1. 题目还原与考点拆解1.1 笔试里的题目长什么样虽然我不能把携程的原题原文一字不差复述出来但我可以负责任地说这题的题型和下面这个描述基本等价给定一个长度为 n 的数组 a定义某个连续子数组 [l, r] 的权值为min(a[l..r]) × gcd(a[l..r])也就是这个子数组的最小值乘以整个子数组的最大公约数。要求所有连续子数组的权值之和结果对 1e97 取模。举个例子。假设 a [6, 10, 15]那么所有连续子数组是[6]min6gcd6贡献 36[10]min10gcd10贡献 100[15]min15gcd15贡献 225[6,10]min6gcd2贡献 12[10,15]min10gcd5贡献 50[6,10,15]min6gcd1贡献 6加起来就是 429样例输出也应该是 429。这种题和“求所有子数组的和”“求所有子数组的最大值”完全不是一个套路。子数组和可以用前缀和 O(1) 做子数组最大值可以用单调栈枚举每个位置作为最大值但现在是 min 再乘上 gcd。gcd 这个东西不满足类似前缀和的简单可减性min 又和 gcd 的分布互相纠缠所以必须想点别的办法。1.2 为什么这题能卡住一批人我在群里看见不少人的第一版代码长这样long long ans 0; for (int l 0; l n; l) { int curMin INT_MAX, curGcd 0; for (int r l; r n; r) { curMin min(curMin, a[r]); curGcd gcd(curGcd, a[r]); ans curMin * curGcd; } }这段代码在 n ≤ 1000 的时候完全没问题逻辑也对稍微优化一下还能做到 O(n²)。问题是笔试数据根本不可能给你 1000 的机会。n 一上来就是 1e5 量级O(n²) 就是 1e10 次操作什么语言都救不回来。所以这题真正的第一个坎是你得意识到暴力不可行然后找到能跳过大量重复计算的性质。第二个坎是 gcd 的变化规律。很多同学知道“一个数不断和其他数取 gcd变化的次数不多”但不知道怎么用。实际上固定一个端点另一个端点往远处移动时gcd 的值每次要么不变要么变成原来某个数的真因子而一个数的真因子最多只有原来的一半所以整条链的长度是 O(log V)V 是数组里最大的值。这个性质才是整个解法的钥匙。2. 两个关键性质先搞定数学再谈代码2.1 gcd 的单调衰减与“段数很少”原理我先解释一个看起来很简单、但很多人没想透的点为什么 gcd 不会一直变来变去。假定我们从左往右扫一个固定右端点每加入一个新元素 x当前的区间 gcd 会变成 gcd(oldGcd, x)。如果 oldGcd 能被 x 整除那么 gcd 不变。如果不能整出新的 gcd 一定是 oldGcd 的真因子而任意一个大于 0 的真因子 d都满足 d ≤ oldGcd / 2。所以你可以把每个位置的“前缀 gcd”看成一条只降不升的链每次真变化至少让值减半。对于 int 范围内的数最多变化 30 多次就到底了。这意味着固定右端点 r随着左端点 l 从 r 往左移动gcd(a[l..r]) 的不同取值段数只有 O(log V) 个。这个结论非常重要它提醒我们哪怕某个区间长度很长从 gcd 的角度看它也只是被少数几段同质区间拼起来的。2.2 子数组最小值用单调栈划分“支配区间”如果说 gcd 的特点是“段数少”那 min 的特点就是“我可以找到每个位置作为最小值时能管到的范围”。这就是单调栈的经典应用。对于每个下标 i我们定义left[i]i 左边第一个「严格小于」a[i] 的位置right[i]i 右边第一个「小于等于」a[i] 的位置为什么一边取严格小于一边取小于等于这是为了处理重复元素。想象数组里有两个 5位置分别是 x 和 y而且 x y。如果左右两边都取严格小于那么区间 [x, y] 里的最小值既会被 x 统计又会被 y 统计必然重复。正确的做法是把重复元素只交给“最左边的那一个”负责。于是左边的边界要放宽只有严格小于才能挡住它右边的边界要收紧遇到小于等于就停下。这样每个子数组的最左最小值唯一它只会被统计一次。有了 left[i] 和 right[i]所有以 i 作为最左最小值的子数组左端点 l 一定落在 (left[i], i]右端点 r 一定落在 [i, right[i])。这一步把 min 维度彻底解决了接下来只需要在这个范围内处理 gcd。2.3 把二维枚举压缩成左右两个 gcd 段列表假设我们已经锁定了 i 是最左最小值那么对于任意合法的 l 和 r整个子数组的贡献是a[i] × gcd(a[l..r])现在把区间 [l, r] 拆开看gcd(a[l..r]) gcd(gcd(a[l..i-1]), a[i], gcd(a[i1..r]))左侧 gcd(a[l..i-1]) 随着 l 从 i 往左移动变化的段数是 O(log V)。右侧 gcd(a[i1..r]) 随着 r 从 i 往右移动变化的段数同样只有 O(log V)。也就是说我们不需要枚举每一个 (l, r) 组合只需要枚举左侧 gcd 的每一段和右侧 gcd 的每一段。这个思想就是把笛卡尔积从 O(n²) 降成了 O(log² V)对于 1e5 的数据量基本等于白给。3. 算法设计与复杂度分析3.1 整体框架三段式预处理整个算法的执行分为三步。第一步用单调栈求出 left[i] 和 right[i]解决 min 的支配范围。这一步 O(n)。第二步预处理出两个数据结构leftSeg[i]以 i 为右端点所有左端点 l ∈ [0, i] 的 gcd(a[l..i]) 分段列表。rightSeg[i]以 i 为左端点所有右端点 r ∈ [i, n-1] 的 gcd(a[i..r]) 分段列表。这两个列表的每个段记录三个信息gcd 值、区间左端点、区间右端点。因为它们都 O(log V) 段总复杂度 O(n log V)。第三步枚举每个 i 作为最左最小值从 leftSeg[i-1] 和 rightSeg[i1] 里各自截取出属于合法范围的段再做一次笛卡尔积累加贡献。3.2 单调栈求左右边界等号细节别写错求 left[i] 和 right[i] 的代码很传统但细节不能错。我统一用“左边严格小于右边小于等于”来保证最左最小值唯一。求左边时维护一个单调递增栈。当栈顶元素大于等于 a[i] 时弹出弹出完之后栈顶就是左边第一个严格小于 a[i] 的位置vectorint left(n); vectorint stk; for (int i 0; i n; i) { while (!stk.empty() a[stk.back()] a[i]) stk.pop_back(); left[i] stk.empty() ? -1 : stk.back(); stk.push_back(i); }求右边时从右往左扫但弹出条件改为栈顶元素大于 a[i]这样遇到相等元素时不会弹出右边第一个小于等于 a[i] 的位置会自然落在相等元素上vectorint right(n); stk.clear(); for (int i n - 1; i 0; --i) { while (!stk.empty() a[stk.back()] a[i]) stk.pop_back(); right[i] stk.empty() ? n : stk.back(); stk.push_back(i); }3.3 左右 gcd 段列表的递推构建这个部分是整个代码最需要耐心的部分但只要理解了“从旧列表推导新列表”就很简单。对于 leftSeg[i]它的意思是固定右端点 il 从 i 往左走gcd(a[l..i]) 的分段。递推关系是这样的新段永远是 (a[i], i, i)对应 l i 这个单元素区间。对于 leftSeg[i-1] 里的每个段 (g, lo, hi)新的 gcd 是 gcd(g, a[i])。这些旧的段本来按 lo 从大到小排列直接追加到新段后面如果相邻段 gcd 值相同就合并。同理rightSeg[i] 从 rightSeg[i1] 递推得到只是方向反一下。为了加深理解拿 a [6, 10, 15] 举例子。leftSeg[2] 的推导过程新段(15, 2, 2)处理 leftSeg[1] [(10, 1, 1), (2, 0, 0)]gcd(10, 15) 5得到 (5, 1, 1)gcd(2, 15) 1得到 (1, 0, 0)所以 leftSeg[2] [(15,2,2), (5,1,1), (1,0,0)]。手动验证一下l2 时 gcd15l1 时 gcd(15,10)5l0 时 gcd(15,10,6)1完全正确。3.4 贡献计算公式与复杂度表枚举到 i 时左侧合法范围内所有可能 l 的 gcd 段构成一个列表 L右侧合法范围内所有可能 r 的 gcd 段构成列表 R。注意左侧 l 可以等于 i此时左侧为空gcd 部分相当于只有 a[i]所以我在 L 的最前面塞了一个 (0, 1) 段长度为 1表示“空区间”。右侧同理。贡献是ans_i a[i] × Σ_{p∈L} Σ_{q∈R} len(p) × len(q) × gcd(g_p, a[i], g_q)其中 gcd(0, x) 在 C 和 Python 的 gcd 函数里都会自然返回 x所以空段不需要额外特判。整体复杂度用一张表总结步骤时间复杂度空间复杂度单调栈左右边界O(n)O(n)leftSeg / rightSeg 预处理O(n log V)O(n log V)枚举 i 合并贡献O(n log² V)O(log V) 临时空间这里的 V 是数组最大值log V 大约 30 左右。实际运行中每一层的段数平均只有 3 到 5 个所以远达不到理论上限。4. 三种语言实现详解4.1 C最省心的性能担当C 版本我用 vector 存段用 tuple 存 gcd 值和区间端点。为了减少拷贝我用 vectortuplelong long,int,int 来表示 leftSeg[i] 和 rightSeg[i]。底层用 bits/stdc.h 方便笔试std::gcd 在 里已经能直接用不需要自己写gcd函数。有一个特别容易踩的坑是取模。单次乘法用 long long 都可能溢出必须边乘边模。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; vectorint left(n), right(n); vectorint stk; for (int i 0; i n; i) { while (!stk.empty() a[stk.back()] a[i]) stk.pop_back(); left[i] stk.empty() ? -1 : stk.back(); stk.push_back(i); } stk.clear(); for (int i n - 1; i 0; --i) { while (!stk.empty() a[stk.back()] a[i]) stk.pop_back(); right[i] stk.empty() ? n : stk.back(); stk.push_back(i); } vectorvectortuplelong long, int, int leftSeg(n); for (int i 0; i n; i) { vectortuplelong long, int, int cur; cur.push_back({a[i], i, i}); if (i 0) { for (auto [g, lo, hi] : leftSeg[i - 1]) { long long ng gcd(g, a[i]); auto back cur.back(); if (get0(back) ng) { get1(back) lo; } else { cur.push_back({ng, lo, hi}); } } } leftSeg[i] cur; } vectorvectortuplelong long, int, int rightSeg(n); for (int i n - 1; i 0; --i) { vectortuplelong long, int, int cur; cur.push_back({a[i], i, i}); if (i 1 n) { for (auto [g, lo, hi] : rightSeg[i 1]) { long long ng gcd(g, a[i]); auto back cur.back(); if (get0(back) ng) { get2(back) hi; } else { cur.push_back({ng, lo, hi}); } } } rightSeg[i] cur; } long long ans 0; for (int i 0; i n; i) { vectorpairlong long, long long L, R; L.push_back({0, 1}); if (i 0) { int border left[i] 1; for (auto [g, lo, hi] : leftSeg[i - 1]) { if (hi border) break; long long len hi - max(lo, border) 1; L.push_back({g, len}); } } R.push_back({0, 1}); if (i 1 n) { int border right[i] - 1; for (auto [g, lo, hi] : rightSeg[i 1]) { if (lo border) break; long long len min(hi, border) - lo 1; R.push_back({g, len}); } } long long sum 0; for (auto [gL, lenL] : L) { for (auto [gR, lenR] : R) { long long g gcd(gcd(gL, a[i]), gR); long long add (lenL % MOD) * (lenR % MOD) % MOD; add add * (g % MOD) % MOD; sum (sum add) % MOD; } } ans (ans (a[i] % MOD) * sum) % MOD; } cout ans \n; return 0; }C 版本在 n 2e5a[i] 都是 1e9 量级时实测跑下来大概在 1 秒上下。如果笔试环境比较紧张记得加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)不然输入都可能拖慢时间。4.2 Java注意 List 与对象开销Java 笔试最恶心的就是每次 new 对象带来的 GC 开销。段的数量是 O(n log V)如果每个段都 new 一个 Seg 对象内存会很难看但一般情况下还能接受。真正要注意的是不要用 List 存中间结果装箱拆箱在 1e5 数据量下会明显变慢。我用静态内部类 Seg 表示段然后用 ArrayList 存所有段。rightSeg 构建时为了避免倒序麻烦我用一个从后往前的循环最后 Collections.reverse 一下。import java.util.*; import java.io.*; public class Main { static final long MOD 1_000_000_007L; static long gcd(long a, long b) { while (b ! 0) { long t a % b; a b; b t; } return a; } static class Seg { long g; int lo, hi; Seg(long g, int lo, int hi) { this.g g; this.lo lo; this.hi hi; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); StringTokenizer st new StringTokenizer(br.readLine()); long[] a new long[n]; for (int i 0; i n; i) a[i] Long.parseLong(st.nextToken()); int[] left new int[n]; int[] right new int[n]; int[] stk new int[n]; int top -1; for (int i 0; i n; i) { while (top 0 a[stk[top]] a[i]) top--; left[i] top 0 ? stk[top] : -1; stk[top] i; } top -1; for (int i n - 1; i 0; i--) { while (top 0 a[stk[top]] a[i]) top--; right[i] top 0 ? stk[top] : n; stk[top] i; } ListListSeg leftSeg new ArrayList(); for (int i 0; i n; i) { ListSeg cur new ArrayList(); cur.add(new Seg(a[i], i, i)); if (i 0) { for (Seg s : leftSeg.get(i - 1)) { long ng gcd(s.g, a[i]); Seg last cur.get(cur.size() - 1); if (last.g ng) { last.lo s.lo; } else { cur.add(new Seg(ng, s.lo, s.hi)); } } } leftSeg.add(cur); } ListListSeg rightSeg new ArrayList(); for (int i n - 1; i 0; i--) { ListSeg cur new ArrayList(); cur.add(new Seg(a[i], i, i)); if (i 1 n) { for (Seg s : rightSeg.get(i 1)) { long ng gcd(s.g, a[i]); Seg last cur.get(cur.size() - 1); if (last.g ng) { last.hi s.hi; } else { cur.add(new Seg(ng, s.lo, s.hi)); } } } rightSeg.add(cur); } Collections.reverse(rightSeg); long ans 0; for (int i 0; i n; i) { Listlong[] L new ArrayList(); L.add(new long[]{0, 1}); if (i 0) { int border left[i] 1; for (Seg s : leftSeg.get(i - 1)) { if (s.hi border) break; int lo Math.max(s.lo, border); long len (long) s.hi - lo 1; L.add(new long[]{s.g, len}); } } Listlong[] R new ArrayList(); R.add(new long[]{0, 1}); if (i 1 n) { int border right[i] - 1; for (Seg s : rightSeg.get(i 1)) { if (s.lo border) break; int hi Math.min(s.hi, border); long len (long) hi - s.lo 1; R.add(new long[]{s.g, len}); } } long sum 0; for (long[] p : L) { for (long[] q : R) { long g gcd(gcd(p[0], a[i]), q[0]); long add (p[1] % MOD) * (q[1] % MOD) % MOD; add add * (g % MOD) % MOD; sum (sum add) % MOD; } } ans (ans (a[i] % MOD) * sum) % MOD; } System.out.println(ans); } }Java 版本最需要注意的就是数据范围。a[i] 读进来是 int 范围内的但乘起来会超 int所以我全用 long。gcd 函数不要用 Math.abs 之类的写法标准欧几里得就行。4.3 Pythonmath.gcd 的 C 实现是小救星说实话如果你是纯 Python 选手这题在笔试现场压力很大。Python 的循环本来就慢哪怕段数只有 30 个二重循环加 math.gcd 的调用开销也比 C 高不少。不过好在 math.gcd 是 C 实现的本身很快所以只要你没有在 Python 层写很多无用循环还是有机会过的。leftSeg 和 rightSeg 我用列表存三元组 (g, lo, hi)。Python 写起来反而比 Java 清爽因为元组不可变合并时直接新建元组替换即可。import sys from math import gcd MOD 10**9 7 def main(): data sys.stdin.buffer.read().split() n int(data[0]) a list(map(int, data[1:1 n])) left [0] * n right [0] * n stk [] for i in range(n): while stk and a[stk[-1]] a[i]: stk.pop() left[i] stk[-1] if stk else -1 stk.append(i) stk [] for i in range(n - 1, -1, -1): while stk and a[stk[-1]] a[i]: stk.pop() right[i] stk[-1] if stk else n stk.append(i) leftSeg [] for i in range(n): cur [(a[i], i, i)] if i 0: for g, lo, hi in leftSeg[i - 1]: ng gcd(g, a[i]) if cur[-1][0] ng: cur[-1] (ng, lo, cur[-1][2]) else: cur.append((ng, lo, hi)) leftSeg.append(cur) rightSeg [None] * n for i in range(n - 1, -1, -1): cur [(a[i], i, i)] if i 1 n: for g, lo, hi in rightSeg[i 1]: ng gcd(g, a[i]) if cur[-1][0] ng: cur[-1] (ng, cur[-1][1], hi) else: cur.append((ng, lo, hi)) rightSeg[i] cur ans 0 for i in range(n): L [(0, 1)] if i 0: border left[i] 1 for g, lo, hi in leftSeg[i - 1]: if hi border: break L.append((g, hi - max(lo, border) 1)) R [(0, 1)] if i 1 n: border right[i] - 1 for g, lo, hi in rightSeg[i 1]: if lo border: break R.append((g, min(hi, border) - lo 1)) s 0 ai a[i] for g1, len1 in L: for g2, len2 in R: g gcd(gcd(g1, ai), g2) s (s (len1 % MOD) * (len2 % MOD) % MOD * (g % MOD)) % MOD ans (ans (ai % MOD) * s) % MOD print(ans) if __name__ __main__: main()Python 版本如果笔试环境是 PyPy1e5 数据大概率能过。但如果用的是 CPython建议现场先判断数据规模如果 n 只有几千随便写暴力都行如果 n 到了 1e5尽量用上面的代码并且少写一层不必要的 list 推导式。5. 笔试实战常见问题与避坑指南5.1 左右边界等号放错会导致重复或漏算这是我最开始写的时候踩的一个大坑。如果左右两边都取“严格小于”两个相等的元素会同时成为区间最左最小值同一个子数组被算两次。如果左右两边都取“小于等于”那可能谁都统计不到某些区间。正确做法是“左严格、右小于等于”或者完全对称的“左小于等于、右严格”。核心原则就一句话重复元素要么全交给最左边的负责要么全交给最右边的负责不能两边都松。我当时是在本地对拍才发现这个问题的因为小数据下重复元素不多答案差一点你可能看不出来但一旦有大量重复值误差会非常大。5.2 取模与溢出乘法顺序不能乱C 比赛时我习惯压行结果有一版代码写成了(lenL * lenR % MOD) * g % MOD。看着没问题但 lenL 和 lenR 都是 1e5 量级乘起来是 1e10还在 long long 范围内再乘 g 就爆了。正确写法是先 mod 再乘保证每一步的中间结果都不超过 1e18。Java 的 long 范围是 9e18 左右1e9 乘 1e9 是 1e18勉强安全但一定不能连续乘三个数再取模。Python 没有溢出问题但取模也得写否则最后数字会大得离谱虽然 Python 大整数能撑住但速度会下降。5.3 对拍自测别信感觉信暴力笔试后我整理了一份暴力版本专门用来和小数据情况下对拍。做法很简单随机生成 n 从 1 到 8 的数组数值范围 1 到 20暴力算一遍答案再用上面的高效算法算一遍答案对比结果。随机跑了几万组两边结果一致我才敢把代码贴到博客里。这里也建议你们以后遇到复杂算法题先写一个暴力对拍器这是成本最低的排错方式。import random from math import gcd def brute(a): n len(a) ans 0 for l in range(n): m 10**18 g 0 for r in range(l, n): m min(m, a[r]) g gcd(g, a[r]) ans m * g return ans for _ in range(10000): n random.randint(1, 8) a [random.randint(1, 20) for _ in range(n)] # 把高效算法和 brute 结果对比5.4 考场上的时间分配建议这类第四题如果你在笔试中已经花了 15 分钟还没有思路我建议先跳过把后面的大题或者前面没做完的题搞定。笔试不是只看单题得分拿到能拿的分比死磕一道难题更重要。但如果你已经想到“gcd 分段”这个方向那就坚持往下推。这道题从有思路到写对代码我大概用了半小时其中一半时间都花在左右边界细节上。所以对于目标是开发岗或算法岗暑期实习的同学建议平时就专门练一练“枚举最小值贡献 另一维度分段”的组合题这种套路在笔试里出现频率非常高。我个人在这道题上还有一个很深的体会很多同学看到 gcd 就以为要背一堆数论模板实际上这题几乎没有用到任何高深数论知识核心就是一个数学观察——“变化次数少”再加上单调栈这个经典工具。只要你明白了 gcd 的变化链是指数级缩短的思路自然就打开了。最后再分享一个小技巧。如果你在考场上一时想不起怎么维护左右 gcd 段可以直接对每个 i 暴力向左和向右扩展统计 gcd 发生变化的位置。虽然最坏情况是 O(n log V)但实际数据通常不会卡满尤其是当数组元素比较随机时这个“半暴力”版本很容易在笔试里骗到大部分分数。当然追求稳过的话还是建议把上面三种语言的完整解法吃透以后遇到类似题目就是送分题了。