★ FEATURED ARTICLE 先承认一个事实看到Maximum GCD on Whiteboard这种题名我最早也以为要模拟一块白板上的交互操作——写数字、擦数字、再来个什么动态展示。真正动手拆解之后才发现白板只是题面包装核心是一个很纯粹的数论枚举题给定若干个正整数最多允许你擦掉其中一个问剩下的数最大公约数最大能到多少。这题放在某算法竞赛平台的 Div.2 轮次里恰好是一道经典的 C 题难度。它考察的东西非常明确GCD 结合律、前缀/后缀预处理以及边界情况的处理。说白了只要你看穿“白板”这层纸解法路径就很固定代码量也很短。本篇文章我就按自己的复盘习惯把题意还原、核心思路、参考代码、常见错误和变体扩展一次讲透尽量让刚接触这种题型的读者也能直接照着复现。1. 题意还原白板、擦除与最大公约数1.1 像做题一样读题面先抽象模型竞赛题面再花哨最后都得被压缩成一条数学描述。以我对这类以Whiteboard为背景的题的通常理解原题最典型的版本是这样的一块白板上依次写下 n 个正整数。你可以选择执行以下操作至多一次擦掉其中一个数也可以选择不擦。目标是使白板上剩余所有数的最大公约数尽可能大输出这个最大可能值。这里必须强调一个容易忽略的点操作是“至多一次”不是“必须一次”。很多人拿到题直接默认要删掉一个数结果漏掉了不删的情况。尤其是当一个数组的全局gcd已经足够大而删除任何一个数都会破坏这个公约数时正确答案恰恰就是全局gcd。这个模型背后考察的核心能力是把一个生活化场景干巴巴地剥成集合操作保留哪些数、删掉哪个数然后求剩余集合的gcd。算法竞赛里大量所谓“阅读理解题”都是这个套路读题时间不应该花在白板上而应该花在搞清楚数据范围和操作限制。1.2 先拿小数据把暴力答案试出来我们直接构造一个例子用于贯穿全文a [6, 10, 15]如果不擦掉任何数gcd(6, 10, 15) 1。如果擦掉6剩下[10, 15]gcd 5。如果擦掉10剩下[6, 15]gcd 3。如果擦掉15剩下[6, 10]gcd 2。所以这组数据的答案是5来自擦掉第一个数。这个例子尽管简单却立刻告诉了我们三件事答案不一定是全局gcd删除操作可能让答案变大。删除不同位置得到的结果不同所以至少要枚举每个位置。一个数在整体gcd里可能是个“破坏者”比如这里的6和10, 15互质删掉它反而让剩下的数共享了更大的公约数。如果数据范围很小比如 n 最大只有几千那直接O(n^2)暴力枚举删除位置、每次重新扫一遍数组求gcd就能过。但这类 Div.2 C 题通常不会这么客气n 往往给到2e5甚至更高所以必须求一个接近O(n)的做法。1.3 数据范围决定了你有多少操作预算不需要知道确切的极限数据也能从题目难度反推如果出题人把 n 放到2e5那O(n^2)就是死路一条如果 n 只有5000那O(n^2 log MAX)也能活。C 题更常见的设定是 n 在2e5量级值域在1e9量级这意味着不能用双层循环。需要O(n)或O(n log MAX)的预处理。存储用int基本足够因为gcd的值不可能超过最大值。求gcd的次数不能太离谱否则log因子叠起来也不小。所以一看到“求删除一个元素后的某某值”这类题我的第一反应就是前缀信息 后缀信息枚举删除点用O(1)的时间把左右两段合并结果算出来。这几乎成了肌肉记忆。2. 核心思路前缀 GCD 后缀 GCD 为什么是对的2.1 先把 GCD 的三个性质写在草稿纸最上面要理解解法先把gcd的性质写全缺一个后面都可能绕晕交换律gcd(a, b) gcd(b, a)结合律gcd(a, b, c) gcd(gcd(a, b), c)单位元gcd(x, 0) x结合律是最关键的一条。它意味着当你需要求“从位置 l 到位置 r 这一整段数的 gcd”时可以拆成“左边一段的 gcd 和右边一段的 gcd”再来一次gcd。也就是说gcd(a[l..r]) gcd(gcd(a[l..mid]), gcd(a[mid1..r]))对任意切分点都成立。这给了我们极大的拆分自由也是前缀/后缀数组能成立的基石。单位元这条很多人会忽略但它对代码影响很大。后面我们让pre[0] 0、suf[n1] 0就是为了自动处理“左边为空”或“右边为空”的情况。因为gcd(0, x) x空段不会污染真实段的计算结果。另外还有一个直觉很管用的性质从集合中删去一个数剩余所有数的gcd只可能变大或者不变。原因是删掉元素后能同时整除所有剩余数的公共因子集合变大了最大公共因子自然只增不减。这个性质虽然不能直接帮我们筛答案但可以用来验证直觉如果某个删除方案让答案变小那一定不是最优的。2.2 暴力的瓶颈到底卡在哪很多人会觉得这也不难枚举删除第 i 个数然后求剩余所有数的 gcd 不就行了问题在于复杂度。如果数组长度是2e5每一次从零开始扫数组求gcd是O(n log V)再乘上枚举的O(n)总复杂度大约是O(n^2 log V)。按2e5的规模粗略估算即便每次扫描只做一次常规算术也是几亿到几十亿级别的操作量在比赛时限内几乎必挂。更关键的是这个暴力方案里存在大量重复计算。删除位置i和删除位置i1时前面i-1个数的 gcd 是完全相同的但我们每次都重新算一遍这显然浪费。于是自然想到两个数组pre[i] gcd(a[1], a[2], ..., a[i]) // 前缀 gcd suf[i] gcd(a[i], a[i1], ..., a[n]) // 后缀 gcd只要这两个数组在O(n)时间内求出来那么删除第i个数后剩余部分的 gcd 就是gcd(pre[i-1], suf[i1])因为剩余部分恰好被分成两个连续区间[1, i-1]和[i1, n]它们的整体 gcd 就是各自 gcd 再取一次 gcd。这就是“前缀 后缀枚举断点”的经典套路。2.3 pre 和 suf 的递推细节前缀 gcd 的求法非常直接pre[0] 0 pre[i] gcd(pre[i-1], a[i])比如a [6, 10, 15]pre[0] 0 pre[1] gcd(0, 6) 6 pre[2] gcd(6, 10) 2 pre[3] gcd(2, 15) 1前缀数组是“越往右越不会变大”的因为每次都是在已有公约数基础上继续取公约数因子集合只会缩小。后缀 gcd 从右往左扫suf[n1] 0 suf[i] gcd(a[i], suf[i1])同样对上例suf[4] 0 suf[3] gcd(15, 0) 15 suf[2] gcd(10, 15) 5 suf[1] gcd(6, 5) 1有了这两个数组我们枚举删除位置i删除1left pre[0] 0right suf[2] 5结果gcd(0, 5) 5。删除2left pre[1] 6right suf[3] 15结果gcd(6, 15) 3。删除3left pre[2] 2right suf[4] 0结果gcd(2, 0) 2。最大值是5和暴力结果一致。整个计算过程没有一次重复扫描枚举也只用O(n)次gcd调用。这种解法代码量很少真正的关键全在于边界定义和“用 0 当单位元”这一手。我身边不少选手第一次写这题WA 都是栽在pre[0]、suf[n1]的初始化上。2.4 为什么不需要求“删除任意一段”有读者可能会问既然gcd满足结合律能不能直接枚举删除一个区间这题不行因为操作限制是“至多擦掉一个数”不是一个区间。如果把限制改成“删除连续的一段”那反而变成了完全不同的题可能要借助线段树维护区间 gcd 和某种双指针思路。所以在动笔之前看清操作限制特别重要。Whiteboard题容易让人脑补出“擦除任意位置”“反复操作”等奇奇怪怪的设定其实原题就是一次擦除代码逻辑也因此被约束得非常简单。3. 参考实现与关键细节3.1 C17 参考代码先给出我用着最顺手的版本完全围绕上面的 pre/suf 思路实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorint pre(n 2, 0), suf(n 2, 0); for (int i 1; i n; i) { pre[i] gcd(pre[i - 1], a[i]); } for (int i n; i 1; --i) { suf[i] gcd(a[i], suf[i 1]); } int ans pre[n]; // 一个都不擦的情况 for (int i 1; i n; i) { int left_gcd pre[i - 1]; int right_gcd suf[i 1]; ans max(ans, gcd(left_gcd, right_gcd)); } cout ans \n; return 0; }这段代码依赖 C17 的std::gcd在numeric头文件里。用bits/stdc.h的话已经包含进去了不需要额外加。3.2 每个关键位置为什么这样写我把容易写错的地方单独挑出来说。数组长度开成n 2不是n 1。因为代码里要访问suf[i 1]当i n时会访问suf[n 1]必须保证这个下标是合法的。pre[i - 1]在i 1时会访问pre[0]也越界不了。统一开n 2是省钱又安全的习惯。pre[0] 0与suf[n 1] 0。这不是随手写的是利用gcd(x, 0) x这个单位元性质。当左边区间为空时left_gcd应该对最终结果毫无贡献0 就是不贡献任何因子的中性值。如果你把pre[0]初始化成 1那删除第一个数时整个结果都会被错误地限制成gcd(1, suf[2])等于把所有可行答案都抹掉几乎全 WA。枚举时从 1 到 n不漏首尾。i 1意味着擦掉第一个数i n意味着擦掉最后一个数。二者都是合法操作不能漏。很多人写for (int i 1; i n; i)或者for (int i 2; i n - 1; i)都会限缩了删除范围造成边界样例失败。答案初始化为pre[n]。对应“一次都不擦”的情况。pre[n]就是所有数的全局 gcd。把这个作为初始答案再在枚举中用max更新就不怕“删除永远不是最优”的情况。3.3 Python 版本与性能提示习惯用 Python 打比赛的话代码同样简洁from math import gcd def solve(): n int(input()) a [0] list(map(int, input().split())) pre [0] * (n 2) suf [0] * (n 2) for i in range(1, n 1): pre[i] gcd(pre[i - 1], a[i]) for i in range(n, 0, -1): suf[i] gcd(a[i], suf[i 1]) ans pre[n] for i in range(1, n 1): ans max(ans, gcd(pre[i - 1], suf[i 1])) print(ans) if __name__ __main__: solve()Python 版本的复杂度同样是O(n log V)但常数比 C 大。如果 n 到2e5Python 通常还能接受如果 n 到1e6你就得考虑 PyPy 或者换 C。math.gcd是内置函数速度和稳定性都远好过自己手写辗转相除能直接调就别自己造轮子。4. 现场最常见的错误与排查记录4.1 五个典型 WA 原因这题乍看简单提交时 WA 率却不低。我把实战中见到的、自己也踩过的错误整理成一份速查表建议提交前逐项过一遍。症状可能原因修复方式删第一个数或最后一个数时答案错误枚举范围写成了[2, n-1]枚举i从1到n所有测试点都得到一个奇怪的 1pre[0]或suf[n1]初始化为 1改成 0极端情况下答案偏小没有比较“不删除”的情况ans初始化为pre[n]小样例正常大测试 TLE对每个删除位置重新扫数组使用 pre/suf 数组数组下标越界或随机值vector 长度开成n 1访问suf[n1]越界长度开n 2其中初始化成 1 这个错误最致命。因为你把“空区间”的中性值从 0 改成了 1任何gcd(1, x)都等于 1等于强制把所有区间的 gcd 变成了 1。如果比赛数据里碰巧某个答案是 1这代码还能蒙对一部分测试点一旦答案不是 1直接全盘崩溃。还有一类错误和gcd运算本身有关——有人为了防 0先判断一下两数是否为 0 再返回逻辑本身没问题但分支写反了遇到a0, b6返回了 0 而不是 6。这类 bug 不会直接导致编译失败但会静默影响 pre/suf 数组每个位置的值调起来特别费时。我的建议是gcd(0, x)当作 x 处理代码直接写gcd(a, b)不要加多余分支。4.2 用对拍脚本验证正确性在赛场上验证这种套路型题目我强烈推荐一个小技巧写一个暴力解和正解然后用小数据随机对拍。暴力逻辑可以完全按题意来from math import gcd from functools import reduce n int(input()) a list(map(int, input().split())) ans 0 # 不删除 ans max(ans, reduce(gcd, a)) for i in range(n): rest a[:i] a[i 1:] ans max(ans, reduce(gcd, rest)) print(ans)正解用 pre/suf 版本。对拍时生成n 10、值域[1, 20]的随机数据只要跑几千组全都一致说明思路和边界基本没问题。这个办法尤其适合在本地排查上面表格里的那些低级错误虽然简单但真能救命。4.3 一个容易被忽视的小坑数组全相等如果数组是[7, 7, 7]那么全局 gcd 是 7删除任何一个数后 gcd 还是 7 中之一也是 7。这个例子能帮你检验边界处理是否正确。pre[n]初始化为 7枚举删除后gcd(pre[i-1], suf[i1])也应该得到 7。但如果你在删除逻辑里不小心多删了一个数或者漏掉了“不删除”的情况就会出错。反过来数组是[2, 4, 8]时删除任何一个数删除 2gcd(4, 8) 4删除 4gcd(2, 8) 2删除 8gcd(2, 4) 2答案其实是 4不能是 8。因为自己本身的[2,4,8]全局 gcd 是 2删除 2 后留下[4,8]gcd 变成 4。这说明删除操作确实能把“公因数本来就很大的两个数”从破坏者手中释放出来。5. 白板题外同类变体与思维迁移5.1 如果允许删任意多个数先说一个常见误区。有人会想删除任意多个数的话答案是不是也只需要把前缀后缀推广一下其实当删除数量不限时问题会退化到一个很不有趣的答案你大可以把除最大值以外的所有数都擦掉剩下一个数而这一个数的 gcd 就是它自身。这样一来最大值就是答案。除非题目额外规定“最后至少保留两个数”或“必须删恰好 k 个”情况才会重新变得复杂。但这类限制和本篇文章的 pre/suf 思路就不一样了可能需要排序、组合枚举或 DP。因此在看到题目时一定要先确认“删除次数”这个硬约束再决定用什么算法。5.2 如果操作是合并两个数的 GCD有些白板题会换一种操作每次选择白板上两个数擦掉它们写上两数的 gcd。重复若干次问最终白板上可能留下的最大值是多少。这个操作和删除一个数不同每次操作会把数字个数减少 1而最终剩下的数的 gcd 其实是由“没有参与合并的数”和“参与合并成一体的一组数”共同决定的。无论怎么合并你最后本质上是把原数组分成了若干组最终答案是这些分组内部 gcd 的 gcd。进一步你会发现如果目标是最大化最终白板上的某个数那往往就是“选择原数组里的某个最大数其余数全部逐步和其他数合并最后写成 gcd 后不影响它”。这和“删任意多个数”又有相似之处。这类变体的共同点仍然是先把操作翻译成集合划分、保留与删除再去套 gcd 结合律。操作再怎么变gcd 本身的代数性质不变你手里的工具就那么多。5.3 前缀后缀模型还能用在哪些地方pre/suf思想不是 gcd 题专属。只要问题满足“把数组切成两段、信息可合并”就能套求删掉一个元素后的最大连续子段和预处理前缀最大子段和、后缀最大子段和枚举删除点后合并左右两段。求删掉一个元素后数组是否有序预处理前缀“递增是否成立”、后缀“递增是否成立”枚举断点判断拼接后是否仍递增。求删掉一个元素后的最长连续相同子段同样可以前缀长度、后缀长度拼接。这类问题的统一套路是单点删除造成的破坏只影响该点两侧预处理整个数组从左往右和从右往左的某种累积信息枚举删除点并 O(1) 合并两边。所以这题虽然披着数论的外衣练的核心却是非常通用的线性预处理能力。6. 最后一点实战体会我个人打完这种题之后最大的感受是Whiteboard类题目的题面往往很唬人但只要你忍住不在白板模拟上浪费时间尽早把操作抽象成“至多删一个数求剩余集合的 gcd”整道题就成功了一半。实际操作中我的做题顺序大致是这样先手算小例子确认答案形式然后把 gcd 的三个性质写在草稿纸上接着立刻写 pre/suf 数组最后用前面那个全相等数组做 mental check。这套流程基本可以在 15 分钟内完成。还有一个小提醒如果你不确定原题的限制到底是最多删一个还是必须删一个建议把两种情况都写进草稿。不删的情况用一个pre[n]作为初始答案就能覆盖而如果题目是“必须删一个”你只需要把ans初始化为一个足够小的值或者直接去掉pre[n]那一项。两者的区别只在初始化不影响枚举逻辑。这种“差之毫厘”的题恰恰是 Div.2 中段题目最常见的风格知识点不难边界坑多代码不长。把这题吃透后面再遇到任何“删除一个位置求合并结果”的题你都能少走很多弯路。
阅读完成 · 觉得有帮助？
