Codeforces #858 : Div2 F2. GCD Master (hard version)

なるほど。
https://codeforces.com/contest/1806/problem/F2

問題

N要素の整数列Aが与えられる。
Aから2要素を選んで抜き取り、そのGCDをAに追加する、という作業をK回繰り返すとき、総和の最大値を求めよ。

解法

N要素を(N-K)個の空でない集合に分けたとき、それぞれのGCDの総和を最大化する問題といえる。
ここで、1個の集合を除くと1要素のみ残すのがベストである。
よって、最後の(K+1)要素を入れる集合をどうするかを考える。

もしAに重複がない場合、Aの昇順K個とあと1個を入れるのが良い。
あとはAの重複分を何個Kの先頭に入れるかを考えればよいが、これはあり得るK要素のGCDを列挙し、それを満たすよう重複分を入れて行くのが良い。

int T;
int N,K;
ll M, A[1010101];
vector<ll> X,Y,G;
vector<__int128> Xs,Ys;
__int128 ma[1010101];
void solve() {
	int i,j,k,l,r,x,y,t; string s;
	
	cin>>T;
	FOR(t,T) {
		cin>>N>>M>>K;
		FOR(i,N) {
			cin>>A[i];
			ma[i]=-1;
			ma[i]<<=120;
		}
		
		sort(A,A+N);
		X.clear();
		Y.clear();
		Xs={0};
		Ys={0};
		G={0};
		
		__int128 ret=0;
		FOR(i,N) {
			if(i&&A[i]==A[i-1]) {
				Y.push_back(A[i]);
				Ys.push_back(Ys.back()+A[i]);
			}
			else {
				X.push_back(A[i]);
				Xs.push_back(Xs.back()+A[i]);
				G.push_back(__gcd(G.back(),A[i]));
			}
		}
		
		ll g=0;
		for(int L=0,R=0;L<min(K,(int)X.size());L=R+1) {
			R=L;
			while(R<X.size()&&G[L+1]==G[R+1]) R++;
			R--;
			__int128 cma=-1;
			cma<<=120;
			for(i=R+1;i<X.size();i++) {
				cma=max(cma,__gcd(G[L+1],X[i])-(__int128)X[i]);
			}
			for(i=R;i>=L;i--) {
				ma[i]=Xs[X.size()]-Xs[i+1]+cma;
				cma=max(cma,__gcd(G[L+1],X[i])-(__int128)X[i]);
			}
		}
		if(Y.size()>=K) {
			ret=max(ret,Xs.back()+Ys.back()-Ys[K]);
		}
		for(x=1;x<=X.size()&&x<=K;x++) {
			y=K-x;
			if(y<0||y>Y.size()) continue;
			ret=max(ret,Ys.back()-Ys[y]+ma[x-1]);
		}
		
		
		string s;
		while(ret) {
			s+='0'+ret%10;
			ret/=10;
		}
		reverse(ALL(s));
		cout<<s<<endl;
		
	}
}

まとめ

何も上限9*10^18までしなくてもいいと思うんだけどな。