yukicoder : No.937 Ultra Sword

問題設定がちょっとややこしいね。
https://yukicoder.me/problems/no/937

問題

整数列Aが与えられる。
ここに対し、以下の処理を任意に繰り返す。

• 異なる値を2つx,yと選び、x xor yを追加する
• 値を1つ選び、2倍の値を追加する
• 自身が追加した要素を消す

1回だけど、A中である要素を選択し、その倍数の値を持つ要素を、全てその値で割ることができるとする。
その後の値の総和の最小値を求めよ。

解法

自身で生成した値は消せるので、最終的にどの値が生成可能か、というのを列挙し、あとはすべての値で実際に割ってみることにする。
あとはこの処理でどんな値を生成できるかだが、2進数において加算の代わりにxorを取った場合のAのGCDとその倍数が候補になる。
GCDはGF2上の掃出し法と同様に求めることができる。
以下のコードでは、倍数もGCDを1～2^17倍したものを実際に総当たりしている。

int N;
int A[101010];
int C[101010];

ll ret[101010];

int GCD(int x,int y) {
	if(x<y) swap(x,y);
	if(y==0) return x;
	int z=y;
	while(__builtin_clz(x)!=__builtin_clz(z)) z<<=1;
	
	return GCD(y,x^z);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll sum=0;
	int g=0;
	FOR(i,N) {
		cin>>A[i];
		g=GCD(g,A[i]);
		C[A[i]]++;
		sum+=A[i];
	}
	ll mi=1LL<<60;
	for(i=1;i<=100000;i++) {
		ret[i]=sum;
		for(j=i;j<=100000;j+=i) {
			ret[i]-=1LL*C[j]*j;
			ret[i]+=1LL*C[j]*(j/i);
		}
		if(i%g==0) mi=min(mi,ret[i]);
	}
	for(int m=1;m<1<<17;m++) {
		ll t=0;
		FOR(i,17) if(m&(1<<i)) t^=(ll)g<<i;
		if(t<=100000) mi=min(mi,ret[t]);
	}
	cout<<mi<<endl;
	
}

まとめ

単にbit vectorを考えるだけでなく、GCDを考えるのは珍しいな。