先交代一下背景。这道题来自2026年携程暑期实习3月29日的笔试，开发岗和算法岗共用一套笔试题，第四题叫做“min和gcd”。我印象里这类岗位笔试四题里通常有一道压轴的数据结构/数学结合题，这一题就很典型：题干极短，但真正动手时能倒下一大批人。题目背后考察的是对区间最小值和区间最大公约数这两个连续性质的理解，以及能不能把“相等”这个看似简单的关系转化成可枚举的结构。无论你投的是Java、C++还是Python，只要有算法基础，这篇解析都能直接拿去做参考。
先说结论：这道题的标准做法是固定右端点，维护所有以该右端点结尾的子数组的gcd分段，再配合RMQ（区间最值查询）做二分统计。整体复杂度O(n log n log A)，A是数组元素的值域。这个复杂度在n = 2e5的笔试数据下，C++和Java都能稳定通过，Python稍紧但优化常数后也能过。
1. 题目拆解：min=gcd到底在问什么
1.1 题目完整描述
给你一个长度为n的整数数组a，你需要统计一共有多少个子数组，满足这个子数组的最小值等于这个子数组所有元素的最大公约数。
形式化地，统计所有区间[l, r]（0 <= l <= r < n）的个数，使得：
- min(a[l], a[l+1], ..., a[r]) == gcd(a[l], a[l+1], ..., a[r])
数据范围我按笔试常见的强度来假设：1 <= n <= 2e5，1 <= a[i] <= 1e9。
注意：这里gcd是整个区间所有数的gcd，不是相邻两个数的gcd。我用实际笔试里遇到的坑提醒一句，读题时千万别理解成“相邻两数的gcd等于min”，那会直接走偏。
1.2 最直观的暴力思路为什么不行
看到统计子数组个数，第一反应必然是枚举左右端点：
for l in 0..n-1: for r in l..n-1: 维护min和gcd，检查是否相等以任意一个端点从左往右扩，都能O(1)维护min和gcd，所以暴力是O(n^2)的。n = 2e5时n^2 = 4e10，不要说笔试，本地暴力跑半小时都未必出结果。
那问题就变成了：能不能利用min和gcd这两个函数的单调性，把枚举量压到O(n log n)甚至O(n log n log A)？
1.3 两个关键性质
先回顾两个事实，它们直接决定了解法方向：
性质1：固定左端点l，随着右端点r向右移动，区间gcd单调不增。
这是因为每加入一个新数，新的gcd = gcd(旧gcd, 新数)，gcd结果只会变小或不变，永远不会变大。
性质2：固定右端点r，随着左端点l向左移动，区间最小值单调不增。
这个更直观：新区间包含了更多数，最小值不可能变大。
这两个性质合在一起的推论是：固定右端点r，把所有以r结尾的子数组按左端点从r往左看，gcd被分成若干个连续段，且段数是O(log A)级别。为什么？因为每一段内gcd相同，而一旦gcd变化，至少会变为原来严格小于一半的因子（最小也要丢弃一个质因子），所以最多变化约log2(A)次。
这个“gcd分段数很少”的性质是整个解法的基石。
2. 核心思路：gcd分段 + RMQ二分统计
2.1 算法框架总览
我的解法流程如下：
- 预处理ST表，支持O(1)查询任意区间[l, r]的最小值。
- 从左到右扫描数组，维护一个列表
segments，表示以当前r结尾的所有子数组，按左端点递增（即从左到右）划分成若干段，每一段内gcd相同。 - 对每个gcd段，段内左端点的区间是[L, R]，该段对应的gcd值是g。
- 问题转化为：在区间[L, R]里，有多少个左端点x，使得
min(a[x..r]) == g。 - 由于固定r时，
min(a[x..r])随x增大（区间缩短）而单调不降，所以在[L, R]内满足等于g的x是一段连续区间。用两次二分分别找到第一个大于等于g的x和第一个严格大于g的x，两者下标之差就是该段贡献的子数组数量。 - 累计所有gcd段的贡献，输出答案。
这个思路的关键在于把“枚举区间”换成了“枚举gcd段”。每个段内不需要再暴力枚举左端点，而是用RMQ+二分快速定位。
2.2 为什么gcd段更新是O(log A)的
假设上一轮（右端点为r-1）的gcd段列表是segments，形如[(g1, L1, R1), (g2, L2, R2), ...]，表示：
- 左端点在[L1, R1]内时，子数组gcd都为g1；
- 左端点在[L2, R2]内时，子数组gcd都为g2；
- 依此类推，且左端点范围从0一直到r-1连续覆盖。
现在新加一个数a[r]，所有以r结尾的子数组，相当于在原来的每个子数组末尾追加了a[r]。因此新的gcd列表就是：
对每个(g, L, R)，新的gcd = gcd(g, a[r]) 同时单独加入一个起点r：gcd(a[r], a[r]) = a[r]合并相邻相同gcd的段，新旧段数之和不会超过原始段数+1。而原始段数本身就是O(log A)，所以每轮维护gcd段的代价是O(log A)。
这里我在实现时用了一个小技巧：不构建新列表再合并，而是直接把旧段的gcd逐个与a[r]取gcd后放入临时列表，末尾追加(a[r], r, r)，再一次遍历合并相邻相同项。
2.3 二分统计的细节推导
固定了右端点r后，定义一个函数：
f(x) = min(a[x], a[x+1], ..., a[r])其中x取值范围是[0, r]。
**f(x)是x的单调不降函数。**直观理解：x越大，区间越短，包含的数越少，最小值越大或不变。
对于一个gcd段，它限制了x必须落在[L, R]内，并且这一段里gcd(a[x..r]) == g。我们要统计有多少个x满足：
f(x) == g由于f(x)单调不降，所有满足f(x) == g的x必然是一个连续区间。用两次二分：
- 第一次二分找第一个满足
f(x) >= g的位置leftIdx。 - 第二次二分找第一个满足
f(x) > g的位置rightIdx。
那么满足f(x) == g的x数量就是rightIdx - leftIdx。如果该区间内根本没有满足条件的x，那么leftIdx会等于rightIdx，贡献为0，不会出错。
有人可能会问：为什么不在gcd段里再遍历一次？因为段长可能到O(n)，而二分查找每次只花O(log n)。整体算下来每个右端点有O(log A)个段，每个段两次二分，总复杂度O(n log n log A)，这才是能撑住2e5数据的核心优化。
2.4 为什么用ST表而不是线段树
查询区间最小值，可以用线段树，也可以用ST表。这个场景我选了ST表，原因是：
- ST表预处理O(n log n)，单次查询O(1)，正好配合二分的大量查询。
- 线段树单次查询O(log n)，会让复杂度多一个log。
- 整个算法只需要区间最小值查询，没有修改操作，ST表完全够用。
ST表核心是倍增思想：用st[k][i]表示从i开始、长度为2^k的区间最小值。查询区间[l, r]时取长度len，令k = floor(log2(len))，则：
min(l, r) = min(st[k][l], st[k][r - 2^k + 1])这里利用了区间重叠不影响最小值计算的性质。
3. 三种语言实现与踩坑提醒
3.1 C++实现
C++版我直接用vector<vector<int>>存ST表，gcd用标准库自带函数，代码可读性和性能兼顾。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; int K = __lg(n) + 1; vector<vector<int>> st(K, vector<int>(n)); st[0] = a; for (int k = 1; k < K; ++k) { int len = 1 << (k - 1); for (int i = 0; i + (1 << k) <= n; ++i) { st[k][i] = min(st[k - 1][i], st[k - 1][i + len]); } } auto getMin = [&](int l, int r) { int len = r - l + 1; int k = __lg(len); return min(st[k][l], st[k][r - (1 << k) + 1]); }; vector<array<int, 3>> seg; long long ans = 0; for (int r = 0; r < n; ++r) { vector<array<int, 3>> nxt; for (auto [g, L, R] : seg) { nxt.push_back({std::gcd(g, a[r]), L, R}); } nxt.push_back({a[r], r, r}); vector<array<int, 3>> merged; for (auto [g, L, R] : nxt) { if (!merged.empty() && merged.back()[0] == g) { merged.back()[2] = R; } else { merged.push_back({g, L, R}); } } for (auto [g, L, R] : merged) { // 第一个 f(x) >= g int lo = L, hi = R + 1; while (lo < hi) { int mid = (lo + hi) >> 1; if (getMin(mid, r) >= g) hi = mid; else lo = mid + 1; } int leftIdx = lo; // 第一个 f(x) > g lo = L; hi = R + 1; while (lo < hi) { int mid = (lo + hi) >> 1; if (getMin(mid, r) > g) hi = mid; else lo = mid + 1; } int rightIdx = lo; ans += rightIdx - leftIdx; } seg = move(merged); } cout << ans << '\n'; return 0; }C++有几个注意点：
std::gcd需要C++17，笔试环境一般支持，如果不支持就自己写欧几里得。array<int, 3>存 {gcd, L, R}，合并时只改R，L保持不变，因为段是连续且覆盖完整区间的。__lg在GCC下可用，如果想更通用，可以手写log2预处理。
3.2 Java实现
Java版本需要注意的点和C++略有不同：没有__lg和结构化绑定，逻辑要写得啰嗦一点，但算法完全一致。
import java.util.*; public class Main { static int n; static int[] a, lg; static int[][] st; static int queryMin(int l, int r) { int len = r - l + 1; int k = lg[len]; return Math.min(st[k][l], st[k][r - (1 << k) + 1]); } static int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n]; for (int i = 0; i < n; ++i) a[i] = sc.nextInt(); lg = new int[n + 1]; for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1; int K = lg[n] + 1; st = new int[K][n]; st[0] = a.clone(); for (int k = 1; k < K; ++k) { int len = 1 << (k - 1); for (int i = 0; i + (1 << k) <= n; ++i) { st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + len]); } } List<int[]> seg = new ArrayList<>(); long ans = 0; for (int r = 0; r < n; ++r) { List<int[]> nxt = new ArrayList<>(); for (int[] t : seg) { nxt.add(new int[]{gcd(t[0], a[r]), t[1], t[2]}); } nxt.add(new int[]{a[r], r, r}); List<int[]> merged = new ArrayList<>(); for (int[] t : nxt) { if (!merged.isEmpty() && merged.get(merged.size() - 1)[0] == t[0]) { merged.get(merged.size() - 1)[2] = t[2]; } else { merged.add(t); } } for (int[] t : merged) { int g = t[0], L = t[1], R = t[2]; int lo = L, hi = R + 1; while (lo < hi) { int mid = (lo + hi) >>> 1; if (queryMin(mid, r) >= g) hi = mid; else lo = mid + 1; } int leftIdx = lo; lo = L; hi = R + 1; while (lo < hi) { int mid = (lo + hi) >>> 1; if (queryMin(mid, r) > g) hi = mid; else lo = mid + 1; } int rightIdx = lo; ans += rightIdx - leftIdx; } seg = merged; } System.out.println(ans); sc.close(); } }Java实现里我建议把gcd写成递归，比循环版可读性更好，笔试时也不容易写错。如果担心递归栈，可以改成循环，但笔试数据量下递归深度不会超过log级别，没问题。
(lo + hi) >>> 1是无符号右移，用来代替/ 2，避免lo+hi溢出，同时速度更快。虽然这里L、R都不会太大，但养成习惯是好的。
3.3 Python实现
Python实现最需要注意的是性能。我的建议是能不用类就不用类，能把循环写成列表推导就写列表推导，ST表查询函数尽量内联。
import sys import math def main(): input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) lg = [0] * (n + 1) for i in range(2, n + 1): lg[i] = lg[i // 2] + 1 K = lg[n] + 1 st = [a[:]] k = 1 while (1 << k) <= n: prev = st[-1] span = 1 << (k - 1) limit = n - (1 << k) + 1 cur = [0] * limit for i in range(limit): v1 = prev[i] v2 = prev[i + span] cur[i] = v1 if v1 < v2 else v2 st.append(cur) k += 1 def query_min(l, r): length = r - l + 1 level = lg[length] row = st[level] v1 = row[l] v2 = row[r - (1 << level) + 1] return v1 if v1 < v2 else v2 seg = [] ans = 0 for r in range(n): nxt = [] for g, L, R in seg: nxt.append((math.gcd(g, a[r]), L, R)) nxt.append((a[r], r, r)) merged = [] for g, L, R in nxt: if merged and merged[-1][0] == g: merged[-1] = (g, merged[-1][1], R) else: merged.append((g, L, R)) for g, L, R in merged: lo, hi = L, R + 1 while lo < hi: mid = (lo + hi) // 2 if query_min(mid, r) >= g: hi = mid else: lo = mid + 1 left_idx = lo lo, hi = L, R + 1 while lo < hi: mid = (lo + hi) // 2 if query_min(mid, r) > g: hi = mid else: lo = mid + 1 right_idx = lo ans += right_idx - left_idx seg = merged print(ans) if __name__ == "__main__": main()Python版本我在实际测试时发现，ST表构建如果直接用：
cur = [min(prev[i], prev[i + span]) for i in range(limit)]其实也够用，但在n = 2e5时列表推导里嵌min函数调用会有额外开销。我改成三目判断后，常数小了一截。整体跑下来，Python在2e5随机数据下大概3到5秒，牛客这类平台可能卡时限，但如果n只有1e5，问题不大。
3.4 三种语言的性能对比
| 语言 | 核心优势 | 需要注意的点 | 预估通过上限（随机数据） |
|---|---|---|---|
| C++ | 性能最强，std::gcd现成 | 记得开ios::sync_with_stdio(false) | n = 2e5 轻松过 |
| Java | 语法直观，List操作顺手 | 避免频繁new int[]，可以用局部变量优化 | n = 2e5 可过 |
| Python | 写起来最快，适合思路验证 | 常数大，ST表构建要手写循环 | n = 1e5 较稳，2e5 有超时风险 |
如果你笔试选的是Python，建议先写出暴力版对拍，再换这个优化版。如果批改环境时限很紧，可以考虑把二分的两次合并成一次：由于第一个f(x) > g的位置也可以从前一次的leftIdx开始找，能省少量常数。
4. 测试用例、对拍与常见问题
4.1 手工样例验证
我自己手算了一组样例来验证思路：
输入： 5 2 4 6 3 6手动枚举满足条件的子数组：
- 长度1：
[2]、[4]、[6]、[3]、[6]，共5个 - 长度2：
[2,4]min=2 gcd=2，满足；[4,6]min=4 gcd=2，不满足；[6,3]min=3 gcd=3，满足；[3,6]min=3 gcd=3，满足，共3个 - 长度3：
[2,4,6]min=2 gcd=2，满足；[4,6,3]min=3 gcd=1，不满足；[6,3,6]min=3 gcd=3，满足，共2个 - 长度4：
[2,4,6,3]min=2 gcd=1，不满足；[4,6,3,6]min=3 gcd=1，不满足 - 长度5：
[2,4,6,3,6]min=2 gcd=1，不满足
总计10个。用上面的三个程序跑，输出都是10。
另一个边界样例：
输入： 4 4 4 4 4所有子数组都满足min=gcd=4。以长度划分：4 + 3 + 2 + 1 = 10。程序输出也是10。
4.2 暴力对拍是必须的
笔试写完后，如果时间允许，我强烈建议立刻写一个O(n^2)的暴力版本，用随机小数据跟优化版对拍。我平时刷题的流程是：
- 写一个暴力函数
solveBrute(a)，枚举所有区间，逐个计算min和gcd。 - 写一个优化函数
solveFast(a)。 - 随机生成n = 20以内的数组，值域1到50，反复对比输出。
- 一旦发现不一致，打印出具体数组，人工分析。
对拍脚本用Python写最方便，一次跑几千组随机数据也就几秒钟。不要觉得这是浪费时间，很多隐藏边界问题只有随机对拍才能暴露出来。比如数组长度为1、所有数全相等、gcd段合并出错等，都能靠对拍快速发现。
4.3 我实际踩过的坑
第一个坑是gcd段合并时忘记更新R。我初版代码里，合并相同gcd段只更新了gcd值，没有把右边界R扩展成当前段的R，导致后面的段区间断开，统计数量直接少了。这个错误在数据量大的时候很难一眼看出，只能靠对拍发现。合并的要点是：相邻两个段gcd相同，说明左端点区间是连续的，合并后的段左边界取前一段的L，右边界取后一段的R。
第二个坑是二分边界没想清楚。我一开始想找的是第一个f(x) >= g的位置，以及最后一个f(x) <= g的位置。但二分法找“最后一个小于等于”不如找“第一个大于等于”和“第一个大于”来得干净。后一种写法天然处理了不存在相等段的情况，代码也更短。
第三个坑是忘记开long long。子数组数量最多是n*(n+1)/2，n = 2e5时约为2e10，int完全不够。Java和C++里我都用了long long或long，只有Python不需要担心这点。
4.4 常见问题速查
| 现象 | 可能原因 | 处理方法 |
|---|---|---|
| 输出比答案小 | gcd段合并后R没更新 | 合并时把右边界改成当前段的R |
| 输出为0或明显偏少 | 二分条件写反 | 检查是>= g还是<= g |
| 大数组超时 | ST表查询内嵌函数调用过多 | 把查询行内联，或改用数组查表 |
| 结果溢出 | 用int统计 | C++/Java改long long/long |
| 单元素数组出错 | 初始化seg为空，走了特殊分支 | 确保每轮都会加入(a[r], r, r)这一项 |
5. 扩展思考：这个思路还能用在哪
“固定右端点 + 维护gcd分段 + 用单调性二分统计”这个套路，在笔试里其实能延伸出不少变体。比如：
- 统计
min == lcm的子数组数量：lcm也有类似的分段递减性质，只是需要用lcm的分段而不是gcd。 - 统计
gcd == x的子数组数量：gcd分段可以直接支持，每个段查一下g是否等于x即可。 - 统计
min * gcd <= K或满足其他不等式的子数组数量：在gcd段内，min的单调性允许你用二分找边界，复杂度依然是O(n log A log n)。
核心要记住的是：分段性质加单调性二分是一套组合拳。gcd、lcm、min、max、and、or这些运算，在固定一个端点时都有“段数不多”或“单调变化”的特征，遇到这类题优先想想能不能维护分段，而不是傻傻枚举区间。
我个人在实际操作中的体会是，这类题最难的其实不是代码，而是把“区间性质”转化成“端点函数单调性”的过程。一旦你意识到固定右端点后，min随左端点变化是单调的，gcd随左端点变化是分段的，整个问题就从一个二维枚举变成了两个一维问题叠加。
如果你接下来要面携程或其他大厂实习，建议把这题吃透之后，把“固定端点 + 分段维护”的经典题都刷一遍：子数组按位与、子数组lcm、子数组gcd等于某值的计数问题。这类题在大厂笔试里出现的频率真的非常高。
