CF1500-35A，Codeforces题库中让无数入门者折戟的思维试金石

CF1500-35A是Codeforces竞赛题库中颇具代表性的入门级思维题，被不少参赛者视为检验基础思维能力的“试金石”，让无数刚接触算法竞赛的入门者栽了跟头，它看似难度不高，却暗藏容易被忽略的逻辑陷阱，并非靠套用基础模板就能轻松解决，十分考验参赛者读题的细致度、逻辑严谨性以及跳出常规思维误区的能力，常被用来提醒新手，竞赛入门阶段不能只死记算法模板，打磨缜密的解题思维才是关键。

在算法竞赛爱好者的圈子里,Codeforces（圈内常简称CF）的Div2难度A题从来都是“签到题”的代名词——大多是考察基础语法、简单逻辑的入门级题目，通常参赛选手开赛后5分钟内就能提交通过，是用来热身、攒初始积分的“送分题”，但题库编号为1500场次的35A题，却成了无数刚入坑算法竞赛的新手记忆里的“第一道坎”，甚至被不少人调侃是“Div2A里的卧底”，这道题就是CF1500-35A。

这道题的题面描述格外简单,简单到第一次读题的人都会下意识觉得“这题有手就行”：给定n个正整数，你每次操作可以选中其中任意两个数，把它们替换成这两个数的最大公约数（gcd），问你能不能通过若干次操作，最终把整个数组变成全是1的数组，如果可以的话输出最少需要的操作次数，不行就输出-1。

刚学完gcd知识点的新手看到题面往往会立刻动笔：首先判断数组里本来有没有1，如果有的话，那答案不就是数组长度减去1的个数吗？毕竟有1的话，每次拿1和旁边的数操作，一次就能把那个数变成1，n个数有k个1，自然只需要n-k次操作，如果数组里没有1呢？那只要整个数组的总gcd不是1，就肯定变不出1，直接输出-1就行——等等，那如果总gcd是1、但数组里没有1的时候，需要多少次操作？

很多人第一次做这道题,就是栽在了这个没考虑到的分支里，有人想当然觉得“总gcd是1的话，肯定存在两个相邻的数gcd是1吧？那操作一次出1，再用n-1次把剩下的数变成1，总共n次不就完了？”结果提交上去直接WA（答案错误），盯着测试点看半天才反应过来：不对啊，gcd为1的两个数不一定相邻啊！比如数组[2,4,3,9]，总gcd是1，但相邻数的gcd分别是2、1、3，确实有相邻gcd为1的数；但如果是数组[6,10,15]呢？三个数两两gcd分别是2、3、5，没有一对的gcd是1，但三个数的总gcd是gcd(6,gcd(10,15))=1，这时候你根本没法一次操作就变出1，得先花两次操作：比如先把前两个数变成gcd(6,10)=2，数组变成[2,15]，再操作一次得到1，前前后后花了2次才变出第一个1，之后再花2次把剩下两个数变成1，总共要4次操作，比之前想的n次多了1次。

这时候大家才回过神来：这道题的核心考点根本不是会不会写gcd函数，而是能不能想到“当数组里没有1、但总gcd为1时，我们需要先找到长度最短的、子数组gcd为1的连续子段”——长度为l的连续子段，要把它操作出1，需要l-1次操作，变出第一个1之后，再花n-1次操作把整个数组变成1，总次数就是(l-1)+(n-1)=n+l-2，比如刚才的[6,10,15]，最短的gcd为1的子段就是整个数组，长度l=3，总次数就是3+3-2=4，刚好和我们手动算的结果一致。

不少人第一次摸透这层逻辑的时候,都会拍一下脑袋：原来这么简单？结果写代码的时候又踩了坑——怎么找最短的gcd为1的连续子段？有人上来就写O(n²)的暴力枚举，左端点从0到n-1，右端点从左端点开始往右扫，维护当前子段的gcd，一旦gcd变成1就记录长度更新最小值，写完觉得n最多也就2000（这道题的数据范围n≤2000），O(n²)肯定能过，结果又因为不会剪枝TLE（超时）：其实当固定左端点往右扩展的时候，子段的gcd是单调不增的，而且每次变化至少会除以一个质因子，所以每个左端点对应的不同gcd值最多只有log(max_a)个，根本不需要扫到数组末尾，一旦gcd变成1就可以直接break，甚至可以用更高效的双指针、按位维护gcd集合的方法把复杂度降到O(n log A)，但对于新手来说，能想到暴力枚举+剪枝，已经算是跨过了这道题的第一道坎。

更有意思的是,很多人过了这道题之后很久，回头再刷的时候还会踩新的坑：比如有人忘了判断数组初始有没有1的情况，上来就直接找最短子段，结果在有1的测试点上算出了比正确答案大很多的结果；有人算总gcd的时候初始值设成了0，导致gcd计算全错；还有人在n=1的边界条件上翻了车——如果数组长度是1，那只要那个数本身是1，答案就是0，否则就是-1，不少人没单独处理这个边界，提交之后又收获了一个WA。

为什么这么一道看起来平平无奇的Div2A题,能成为这么多人的“竞赛记忆点”？其实本质上它刚好戳中了算法竞赛新手最容易犯的毛病：读题想当然，觉得题面简单就不肯沉下心拆解所有情况，学了几个基础算法就想直接套，不肯沉下心从最朴素的逻辑出发推导问题，很多人刚入坑的时候总觉得“难题就是要考复杂的数据结构、冷门的算法”，但CF1500-35A偏偏告诉你：哪怕只考gcd的性质，只要藏两个思维上的小弯，就能筛掉一大半不肯认真想问题的参赛者。

现在去翻这道题的提交记录,还能看到各种有意思的评论：有人说“我当年第一次打CF就是这场，这道题卡了我一个半小时，最后比赛结束都没做出来，当场怀疑自己是不是适合学算法”；有人调侃“这道题的难度标错了吧，说它是Div2B我都信，放在A题位置纯粹是出题人搞心态”；还有人把这道题当成“入门验金石”——如果一个新手能靠自己独立想明白这道题的所有情况，不看题解一次写对，那说明他已经跨过了“只会套模板”的初级阶段，开始真正具备算法竞赛需要的思维能力了。

说穿了,CF1500-35A从来不是什么“难题”，它就像学数学的时候遇到的第一道“拐小弯”的应用题：公式你都背过，知识点你都学过，但能不能做对，全看你有没有真的理解问题本质，有没有静下心把所有情况考虑周全，很多人打了好几年CF，攒了一堆高难度题的AC记录，回头看到1500-35A这个编号，还是会想起当年刚入坑时，对着屏幕抓耳挠腮，第一次明白“算法竞赛考的不是背书，是思考”的那个下午。