我们将gcd为\(1\)的相邻两个数连边,比如

最初的\(ans\)就是边的总数

我们考虑一次操作最多让两条边消失。我们将这些边看成若干连通块(比如上面这幅图就有两个连通块,分别有三条边和一条边)。对于一个连通块若含有偶数条边,显然我们每次操作都可以让两条边消失,若含有奇数条边,最后要剩下一条边

所以我们先把所有的连通块处理了,来看看剩下了多少条边以及剩余了多少次操作次数,比较即可

这个算法对吗?对了一半

我们的前提——一次操作让两条边消失——是要没有数为\(1\)的情况下才成立的。现在有了\(1\)怎么办?

我们稍微修改一下就好了,将所有\(1\)独立成连通块,比如

那么对于非\(1\)的块,我们仍然执行上面的算法,然后来考虑剩余的边

对于全\(1\)的块,设其有\(num\)\(1\),那么我们每执行一次操作会让\(ans\)\(1\),但是如果执行了\(num\)次操作,\(ans\)总共会少\(num+1\)(其实这里有一种特殊情况,就是这个块的左端点为\(1\)或者右端点为\(n\),此时执行\(num\)次操作\(ans\)还是只会减少\(num\)次)(其实还有一种最特殊的情况就是所有\(a_i\)都是\(1\),此时我们特殊判断就好了)。所以我们肯定按照全\(1\)块的长度排序,优先处理长度较小的全\(1\)

如果所有全\(1\)块都处理完了还有次数没有用,我们再来考虑最开始的长度为偶数的非\(1\)块(这种块有奇数条边,所以最后会剩下一条边)剩下的边即可