贪心、最大公约数与最小公倍数
读题。读题。读题。读题。读题。读题。读题。读题。读题。读题。读题。
猜测 $\min\limits_{i=1}^{n} a_i$ 肯定放在 $a_1$ 这个位置。证明我自己不会写，放在代码后边。
每次添加元素都贪心最小化前缀 $\gcd$，因为 $\gcd$ 是单调的，能最小化就最小化绝对最优。
如何最小化前缀 $\gcd$ 是一个问题，而且我也想复杂了。
不过终究还是想对了，分解得到 $\min\limits_{i=1}^{n} a_i$ 的所有因子，前缀 $\gcd$ 必定为 $\min\limits_{i=1}^{n} a_i$ 因子。
对于每个因子 $k$ 求出 $\min\limits_{i=1}^{n}\gcd(k,a_i)$ 的值，使用 $go_k$ 表示这个值，如果 $go_k \neq k$ 则必定能通过在当前确定的序列前缀后加入一个从未加入的元素将前缀 $\gcd$ 的值从 $k$ 降低至 $go_k$，否则序列的前缀 $\gcd$ 不能再被降低。
时间复杂度 $O(n d(V) \log n + n d(V) \log V + \sqrt{V})$。我的实现有点拉了，实际上因为 $\gcd$ 最多降低 $O(\log V)$ 次可以做到 $O(n \log V)$。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100'005];
long long ans;
void solution(){
cin>>n,ans=0ll,m=INT_MAX;
for(int i=1;i<=n;i++) cin>>a[i],m=min(m,a[i]);
vector<int> p;
for(int i=1;i*i<=m;i++) if(m%i==0){
p.push_back(i);
if(i*i!=m) p.push_back(m/i);
}
map<int,int> go;
for(int i:p) go[i]=INT_MAX;
for(int i:p) for(int j=1;j<=n;j++) go[i]=min(go[i],__gcd(i,a[j]));
for(int i=1;i<=n;i++) ans+=m,m=go[m];
cout<<ans<<'\n';
}
int T;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--) solution();
return 0;
}所以为啥 $\min\limits_{i=1}^{n} a_i$ 放在首位一定对？感性理解只能感觉这是对的，我需要理性证明。
题解看不懂遂问 zmy123456 大师，他给出了答案。
考虑调整法，如果对于当前的序列 $a_1,a_2,\cdots,a_k,\cdots,a_n$ 存在 $a_1 > a_k$ 则交换 $a_1,a_k$ 必定更优。
为啥？对于所有小于 $k$ 的正整数 $i$，前缀 $a_1,a_2,\cdots,a_i$ 的 $\gcd$ 必定不超过交换后前缀 $a_k,a_1,\cdots,a_i$ 的 $\gcd$，这是一个错位比较，比的是交换前序列的第 $i$ 个前缀和交换后序列的第 $i+1$ 个前缀。
现在还没比较的是交换前序列的第 $k$ 个前缀和交换后序列的第 $1$ 个前缀。
显然 $\gcd\limits_{i=1}^{k} a_i \leq a_k$，那又怎样证明了，如何证明了？
考虑交换前序列的第 $1$ 个前缀和交换后序列的第 $2$ 个前缀使答案减少的值 $a_1 - \gcd(a_1,a_k)$，证明这个值大于交换使答案增加的值 $a_k - \gcd\limits_{i=1}^{k} a_i$ 即可，作差。
$$(a_1 - \gcd(a_1,a_k)) - (a_k - \gcd\limits_{i=1}^{k} a_i) = a_1 - a_k - \gcd(a_1,a_k) + \gcd\limits_{i=1}^{k} a_i$$
由 $\gcd(x,y) \leq \min(x,y)$ 得到
$$a_k + \gcd(a_1,a_k) = a_k + \gcd(a_1 - a_k,a_k) \leq a_k + \min(a_1 - a_k,a_k) \leq a_1$$
将 $a_k + \gcd(a_1,a_k)$ 放大到 $a_1$，原式变为
$$a_1 - a_1 + \gcd\limits_{i=1}^{k} a_i = \gcd\limits_{i=1}^{k} a_i > 0$$
所以若存在 $k \in [1,n] \cap \mathbb{Z}$ 满足 $a_1 < a_k$，交换 $a_1,a_k$ 一定能使答案变优。
于是应当不断调整直到序列中不存在比 $a_1$ 更小的数，所以 $\min\limits_{i=1}^{n} a_i$ 要放在首位，证毕。
这里是对于读错的题的思考过程。
首先有一个观察：无论如何改变顺序，最终得到的 $\gcd$ 序列中本质不同的元素至多只有 $O(\log V)$ 个，因为序列的前缀 $\gcd$ 每次发生改变都至少减少到原来的二分之一。
考虑如果确定了 $a_1$ 的值该怎么样添加 $a_2 \sim a_n$ 来最大化答案。
每次添加元素时能保持当前 $\gcd$ 不变肯定是最好的，那么首先应该在 $a_1$ 后添加所有是 $a_1$ 的倍数的数。现在考虑加完这些数之后能干嘛。
由于加完了 $a_1$ 的倍数，再添加一个数必定会让 $\gcd$ 减少。由于 $\gcd$ 是一个定值，让它减小到原来的二分之一应该是最优的。否则就减小到原来的三分之一，四分之一，显然的策略。
但是这真对吗？是否存在一种策略会仅让 $\dfrac{\gcd}{2}$ 出现一次之后整个序列的 $\gcd$ 变成 $1$；而如果让当前 $\gcd$ 变为 $\dfrac{\gcd}{3}$ 可以维持这个值到整个序列结束呢？令 $G$ 为当前序列前缀 $\gcd$，再令 $X = \dfrac{G}{2},Y=\dfrac{G}{3}$，显然无法让序列前缀 $\gcd$ 从 $X$ 变成 $Y$，因为 $Y$ 比 $X$ 多一个因子 $2$，此路似乎不通啊。
回到开头，既然已经在 $a_1$ 后面添加了 $a_1$ 的倍数来保证 $\gcd$ 不变，那为什么不首先添加 $a_1$ 的倍数来让靠前的前缀 $\gcd$ 更大呢？据此能得到一个保证正确的结论：最终序列的 $a_1$ 不可能是序列中任何数的真因子。
既然 $a_1$ 不是其他任何数的真因子，那么序列肯定存在一个所有等于 $a_1$ 的元素构成的前缀，放完这些数之后放任何数都会导致 $\gcd$ 减小，问题又变回了最初的形式：对于给定的 $a_1$，如何安排后面的数使得所有前缀 $\gcd$ 之和最大？
到这我真不会了。
观察题解发现我读错题了，这个是要最小化序列前缀 $\gcd$ 之和的。