先交代一下背景。这道题来自2026年携程暑期实习3月29日的笔试开发岗和算法岗共用一套笔试题第四题叫做“min和gcd”。我印象里这类岗位笔试四题里通常有一道压轴的数据结构/数学结合题这一题就很典型题干极短但真正动手时能倒下一大批人。题目背后考察的是对区间最小值和区间最大公约数这两个连续性质的理解以及能不能把“相等”这个看似简单的关系转化成可枚举的结构。无论你投的是Java、C还是Python只要有算法基础这篇解析都能直接拿去做参考。先说结论这道题的标准做法是固定右端点维护所有以该右端点结尾的子数组的gcd分段再配合RMQ区间最值查询做二分统计。整体复杂度O(n log n log A)A是数组元素的值域。这个复杂度在n 2e5的笔试数据下C和Java都能稳定通过Python稍紧但优化常数后也能过。1. 题目拆解mingcd到底在问什么1.1 题目完整描述给你一个长度为n的整数数组a你需要统计一共有多少个子数组满足这个子数组的最小值等于这个子数组所有元素的最大公约数。形式化地统计所有区间[l, r]0 l r n的个数使得min(a[l], a[l1], ..., a[r]) gcd(a[l], a[l1], ..., a[r])数据范围我按笔试常见的强度来假设1 n 2e51 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]) 同时单独加入一个起点rgcd(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[x1], ..., 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版我直接用vectorvectorint存ST表gcd用标准库自带函数代码可读性和性能兼顾。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; int K __lg(n) 1; vectorvectorint st(K, vectorint(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]); }; vectorarrayint, 3 seg; long long ans 0; for (int r 0; r n; r) { vectorarrayint, 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}); vectorarrayint, 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需要C17笔试环境一般支持如果不支持就自己写欧几里得。arrayint, 3存 {gcd, L, R}合并时只改RL保持不变因为段是连续且覆盖完整区间的。__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]); } } Listint[] seg new ArrayList(); long ans 0; for (int r 0; r n; r) { Listint[] 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}); Listint[] 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避免lohi溢出同时速度更快。虽然这里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]min2 gcd2满足[4,6]min4 gcd2不满足[6,3]min3 gcd3满足[3,6]min3 gcd3满足共3个长度3[2,4,6]min2 gcd2满足[4,6,3]min3 gcd1不满足[6,3,6]min3 gcd3满足共2个长度4[2,4,6,3]min2 gcd1不满足[4,6,3,6]min3 gcd1不满足长度5[2,4,6,3,6]min2 gcd1不满足总计10个。用上面的三个程序跑输出都是10。另一个边界样例输入 4 4 4 4 4所有子数组都满足mingcd4。以长度划分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*(n1)/2n 2e5时约为2e10int完全不够。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等于某值的计数问题。这类题在大厂笔试里出现的频率真的非常高。
min=gcd子数组计数：gcd分段+RMQ+二分高效解法
先交代一下背景。这道题来自2026年携程暑期实习3月29日的笔试开发岗和算法岗共用一套笔试题第四题叫做“min和gcd”。我印象里这类岗位笔试四题里通常有一道压轴的数据结构/数学结合题这一题就很典型题干极短但真正动手时能倒下一大批人。题目背后考察的是对区间最小值和区间最大公约数这两个连续性质的理解以及能不能把“相等”这个看似简单的关系转化成可枚举的结构。无论你投的是Java、C还是Python只要有算法基础这篇解析都能直接拿去做参考。先说结论这道题的标准做法是固定右端点维护所有以该右端点结尾的子数组的gcd分段再配合RMQ区间最值查询做二分统计。整体复杂度O(n log n log A)A是数组元素的值域。这个复杂度在n 2e5的笔试数据下C和Java都能稳定通过Python稍紧但优化常数后也能过。1. 题目拆解mingcd到底在问什么1.1 题目完整描述给你一个长度为n的整数数组a你需要统计一共有多少个子数组满足这个子数组的最小值等于这个子数组所有元素的最大公约数。形式化地统计所有区间[l, r]0 l r n的个数使得min(a[l], a[l1], ..., a[r]) gcd(a[l], a[l1], ..., a[r])数据范围我按笔试常见的强度来假设1 n 2e51 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]) 同时单独加入一个起点rgcd(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[x1], ..., 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版我直接用vectorvectorint存ST表gcd用标准库自带函数代码可读性和性能兼顾。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; int K __lg(n) 1; vectorvectorint st(K, vectorint(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]); }; vectorarrayint, 3 seg; long long ans 0; for (int r 0; r n; r) { vectorarrayint, 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}); vectorarrayint, 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需要C17笔试环境一般支持如果不支持就自己写欧几里得。arrayint, 3存 {gcd, L, R}合并时只改RL保持不变因为段是连续且覆盖完整区间的。__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]); } } Listint[] seg new ArrayList(); long ans 0; for (int r 0; r n; r) { Listint[] 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}); Listint[] 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避免lohi溢出同时速度更快。虽然这里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]min2 gcd2满足[4,6]min4 gcd2不满足[6,3]min3 gcd3满足[3,6]min3 gcd3满足共3个长度3[2,4,6]min2 gcd2满足[4,6,3]min3 gcd1不满足[6,3,6]min3 gcd3满足共2个长度4[2,4,6,3]min2 gcd1不满足[4,6,3,6]min3 gcd1不满足长度5[2,4,6,3,6]min2 gcd1不满足总计10个。用上面的三个程序跑输出都是10。另一个边界样例输入 4 4 4 4 4所有子数组都满足mingcd4。以长度划分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*(n1)/2n 2e5时约为2e10int完全不够。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等于某值的计数问题。这类题在大厂笔试里出现的频率真的非常高。