洛谷U389682 最大公约数合并

这道题最后有一个性质没有想出来，感觉还是有一点遗憾。

性质一、贪心是不对的

8 11 11 16

虽然第一次选择8和16合并是最优的，但是如果合并两次的话8 11 11是最优的。

性质二 、有1的情况就是前k+1个，也就是说，很多情况下取前k+1都是最优的

性质三 如果某个数前面有它的因子，那么合并的时候可以不对$a_1$产生任何影响。同时，如果$b\mathrm{mod}a=0,b>a$那么$b$一定比$a$后合并,也就是说无影响合并只会发生在相同的数之间，因此我们把无影响的数提出来考虑，所以剩下的都是不同的。

性质四 如果所有的数都不同，那么全部都只会和$a_1$合并。在原来的数列中考虑合并形成的连通块。在连通块大小为2的情况时。设$a1<x<y$，那么有$y-x>=gcd(x,y)$所以,$x+y-gcd(x,y)>=2x>a_1+x$，不如直接合并$a_1$和$x$。现在考虑连通块大小超过2的情况。假设某个连通块不包含$1$，那么我们可以通过合并使得该联通块剩下两个数，其中有一个还没有与任何的数合并。Case 1: $x<a_1<y$，这时应该合并$x,a_1$最优，与原假设矛盾。Case 2: $a_1<=x<=y$，这时也是合并$a_1,x$更优，所以假设错误。

所以，现在应该把前面有相同的和剩下的全部不同的数分成两个组，然后给这两组分配合并次数，难点就是要怎么求在给定的次数时全部不同组的选择方法，但是我没有坚定的往这个方面想。

性质五 假设给全部不同的数合并$k$次，那么必然选择$1,2,...,k-1$，只有第$k$个是不确定的。考虑选择$a,b,c,d(a<b<c<d)$的情况，那么合并如果是$a,c,d$的话，那么$cost(a,c,d)-cost(a,b,c)=d-b+gcd(a,c,d)-gcd(a,b,c)>=gcd(b,c)+gcd(c,d)+gcd(a,c,d)-gcd(a,b,c)>0$，所以只用考虑第k个点怎么选，而且枚举范围有$a[i]-a[k-1]<gcd(a_1,a_2,...,a_{k-1})$，这样显然是不超过$O(nlogn)$的。