題目鏈接：F1 - GCD Master、F2 - GCD Master

題目大意：給定 \(n,m,k(1\le k\lt n \le 10^6,1\le m\le 9\cdot 10^{18})\) 以及一個長度為 \(n\) 的序列 \({a_i}(1\le a_i\le m)\)。每次操作可以選取兩個數 \(x,y\) 從序列中刪去，并將 \(\gcd(x,y)\) 加入序列中。求進行恰好 \(k\) 次操作后 \(\sum a_i\) 的最大值。

分析題目性質

顯然如果序列中存在相同的兩個元素，那么可以通過對這兩個相同元素進行操作，把他們合并成一個元素并消耗一次操作次數，于是我們先假設所有元素都互不相同，思考如何解題。

考慮這么一件事情，如果一開始選了兩個數 \(x,y\) 并將其合并為 \(\gcd(x,y)\) 加到了序列中，之后我們再把這個 \(\gcd\) 拿出來去和另一個數字 \(z\) 合并。那么這一系列操作就相當于把 \(x,y,z\) 三個數字從序列中刪去，并在序列中加入新數字 \(\gcd(x,y,z)\)。于是我們可以把操作分成若干組，每組操作就相當于選取 \(t\) 個數字從序列中刪去，然后把這 \(t\) 個數字的 \(\gcd\) 加入到序列中，一組操作所花費的操作次數就是 \(t-1\) 次。

可以很自然地想到，若劃分的組數越多，被波及的數字個數就越多，于是就會有一個猜想：是否一次性選取 \(k+1\) 個數字把他們合并就是最優的。我們來證明這個猜想。

猜想 1：一次性選取 \(k+1\) 個元素進行合并是最優策略

考慮反證法，如果操作的組數有多組，那么考慮其中兩組操作。不妨設第一組操作涉及到的數字集合為 \(S\)，各個數字的 \(\gcd\) 為 \(x\)；第二組操作涉及的數字集合為 \(T\)，\(\gcd\) 為 \(y\)，且有 \(x\ge y\)。那么這兩組操作帶來的貢獻就是 \(x+y-\sum_{i\in S}{i}-\sum_{j\in T}{j}\)。

接下來觀察把這兩組操作進行合并對貢獻造成的影響。選取 \(S\) 中最大的數字 \(mx\)，由于不可重集 \(S\) 中的 \(\gcd\) 為 \(x\) 且 \(|S|\ge 2\)，所以有 \(mx\ge 2x\)。考慮將 \(mx\) 從 \(S\) 中刪除（即不對該數字進行操作），并對 \(S,T\) 各自合并后的結果 \(x,y\) 進行一次操作，那么在操作次數不變的情況下，其貢獻為 \(\gcd(x,y)-\sum_{i\in S}{i}-\sum_{j\in T}{j}+mx\)。

對比兩種操作的貢獻，去除掉相同的部分有 \(mx+\gcd(x,y)\gt 2x\ge x+y\)，得出后者更優。于是最優方案下的操作組數只會有一組，即得證。

題意轉換

猜想得到證明后，我們就能將題意轉化為：選 \(k+1\) 個數字將他們合并成這些數字的 \(\gcd\)，求代價最少的方案。當然，這里有個前提是序列中的元素各不相同。

考慮有相同元素怎么辦。實際上如果有相同的元素出現在同一組操作中，可以看做先把相同的元素合并成一個元素，剩下的是互不相同的元素一起操作。那么每次把兩個相同元素合并的代價就是對應元素的值。

于是可以把重復的數字拎出來并排序，令 \(b_i\) 表示刪去 \(i\) 個重復元素的最小花費。枚舉 \(i\) 的值，計算一次性選 \(k-i+1\) 個數字合并的最小花費就能得到最終的答案。

在這一系列轉換過后，我們要解決的問題就變成了：對每個 \(i\le k+1\)，求選擇 \(i\) 個數字合并成他們的 \(\gcd\) 的最小花費。

簡單版本：\(m\le 10^6\)

由于值域只有 \(10^6\)，那么就有一個經典的做法就是枚舉 \(\gcd\) 的值，之后判斷 \(\gcd\) 的每個倍數是否存在并計算即可。計算答案部分的時間復雜度為 \(O(m\log m)\)。

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
int T,n,m,k,x,cnt,c[N];
long long sum,ans,b[N];
void init()
{
	cnt=sum=ans=0;
	scanf("%d%d%d",&n,&m,&k);
	k++;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		c[x]++;
		sum+=x;
		if(c[x]>1)b[++cnt]=x;
	}
	sort(b+1,b+cnt+1);
	for(int i=1;i<=cnt;i++)b[i]+=b[i-1];
	if(cnt>=k-1)ans=max(ans,sum-b[k-1]);
	for(int i=1;i<=m;i++){
		long long res=i;
		for(int j=i,num=0;j<=m && num<k;j+=i)if(c[j]){
			res-=j,num++;
			if(cnt>=k-num)ans=max(ans,sum+res-b[k-num]);
		}
	}
	for(int i=1;i<=m;i++)c[i]=0;
	printf("%lld\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--)init();
}

硬版本

對于硬困難版本，由于值域是 \(9\cdot 10^{18}\)，我們不能枚舉 \(\gcd\) 的值求解，于是需要繼續大力分析。

現在不妨設去重后的序列 \({a_i}\) 是有序的，思考我們在簡單版本下枚舉 \(\gcd\) 的值并求解的過程，顯然在 \(\gcd\) 的值確定時，選取最小的幾個數字一定是最優的。而在我們不確定 \(\gcd\) 的值的時候，直接選取最小的若干個數字合并可能就會導致被選取數字的 \(\gcd\) 出現斷崖式下降，使得最終的答案變劣。但有些時候 \(\gcd\) 下降帶來的損失我們又是能接受的，于是考慮對選取方案進行一步步調整，并逐步得到最優解。

調整選取方案

假設一組操作中選取的數字個數為 \(t\)，被選中的數字為 \(a_{i_1},a_{i_2},...,a_{i_t}(i_{j}<i_{j+1})\)，這些數字的最大公約數為 \(d\)，考慮如何調整使代價減小。那么調整的方式就是在這些數字中刪掉一個數，再找一個數替換進來，代價的變化就是這兩個數字之間的差值減去調整前后 \(\gcd\) 的差值。

基于這種調整方式來考慮，我們選擇刪掉最大的數字 \(a_{i_t}\)，并加入最小的未被選到的 \(a_x\)，那么代價的變化量即為 \(a_{i_t}-a_x-d+\gcd(d,a_x)\)。注意到，由于原先這些數字的 \(\gcd\) 為 \(d\)，所以一定有 \(a_{i_t}-a_{i_{t-1}}\ge d\)。那么若有 \(x\lt i_{t-1}\)，就有 \(a_{i_t}-a_x-d+\gcd(d,a_x)\ge a_{i_t}-a_{i_{t-1}}-d+\gcd(d,a_x)\gt 0\)，在這種情況下這樣調整就可以使答案更優。

那么什么時候不能這樣調整呢？顯然這時一定會滿足：不存在未被選擇的下標 \(x\) 使得 \(x\lt i_{t-1}\)。這個命題其實就等價于對任意 \(j\le t-1\)，有 \(i_{j}=j\)。相當于我們先選數組中最小的 \(t-1\) 個數，再選擇一個數字使得答案最優，于是我們得到了一個已經被證明了的猜想。

猜想 2：若需要選取一組 \(t\) 個數字進行操作，則最優方案一定包含序列中最小的 \(t-1\) 個數

采用反證法即可證明，若存在 \(i\le t-1\) 使得 \(a_i\) 未被選擇，則根據之前的調整方案進行調整可使答案更優，即得證。

算法優化

根據已有結論，令 \(g_i\) 表示序列中前 \(i\) 個數的 \(\gcd\)，\(S_i\) 表示序列 \({a_i}\) 的前綴和。那么本題的做法就是枚舉需要合并的數字個數 \(i\)，得出需要刪除的重復數字個數 \(k-i+1\)，對應的最優解就是 \(\underset{x\in [i,n]}{\max} \{Sum-S_{i-1}-a_x+\gcd(g_{i-1},a_x)-b_{k-i+1}\}\)，其中 \(Sum\) 表示初始序列的元素之和。

那么可以發現，對每個 \(i\)，我們要求的就是最大的 \(\gcd(g_{i-1},a_x)-a_x\)，直接做肯定會寄。但是由于前綴 \(\gcd\) 有個性質就是值相同的段數是 \(O(\log m)\) 級別的，所以可以對每一段相同的 \(g_i\) 暴力枚舉 \(x\) 求解，時間復雜度為 \(O(n\log^2m)\)。

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define LL long long
int T,n,k,t,cnt,c[N],p[N];
__int128 sum,ans,S[N],b[N];
LL m,a[N],g[N];
set<LL>s;
void out(__int128 x)
{
	if(x>9)out(x/10);
	printf("%c",(char)('0'+x%10));
}
void init()
{
	s.clear();
	t=cnt=sum=ans=0;
	scanf("%d%lld%d",&n,&m,&k);
	k++;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
		if(s.count(a[i]))b[++cnt]=a[i];
		s.insert(a[i]);
	}
	n=0;
	for(auto i:s)a[++n]=i;
	sort(b+1,b+cnt+1);
	for(int i=1;i<=cnt;i++)b[i]+=b[i-1];
	if(cnt>=k-1)ans=max(ans,sum-b[k-1]);
	for(int i=1;i<=n;i++){
		S[i]=S[i-1]+a[i];
		g[i]=__gcd(a[i],g[i-1]);
		if(g[i]!=g[i-1])p[++t]=i;
		if(cnt>=k-i && k>=i)ans=max(ans,sum+g[i]-S[i]-b[k-i]);
	}
	p[t+1]=n+1;
	for(int i=1;i<=t;i++){
		__int128 mx=-sum;
		for(int j=p[i+1];j<=n;j++)
			mx=max(mx,(__int128)__gcd(g[p[i]],a[j])-a[j]);
		for(int j=p[i];j<min(p[i+1],k);j++)
			if(k-j-1<=cnt)ans=max(ans,sum+mx-S[j]-b[k-j-1]);
	}
	out(ans);
	printf("\n");
}
int main()
{
	scanf("%d",&T);
	while(T--)init();
}