题解：CF1980D GCD-sequence

· · 题解

这是一道简单但是充满细节的的题。

我们先看一下数据范围：3 \leq n \leq 2 \times 10^5。若时间复杂度为 \mathcal{O}(n^2)，显然在时间上是过不去的。

那么我们怎么判断一个数是否应该删除呢？可以定义一个长度为 n - 1 的序列 GCD_i 使得 GCD_i=\gcd(shu_i,shu_{i+1})。这个时候我们需要从前往后看看哪个地方使得 GCD_i > GCD_{i+1}，同理，也从后往前扫一遍，并分别用两个数组记录下来即可。最后一步从 1 \sim n 挨个特判一遍，判断前一个和后一个是否都合法，还要判断前一个和后一个是否能接上，注意首项和末两项的特判。这就是这个题的完整思路。

AC code