AT_abc347_d 的题解

（一）

数学题。

根据 \(C\) 的值，可以得出 \(x\) 和 \(y\) 有 \(s1+s\) 个相同的数位和 \(s2\) 个不同的数位。

\(s1\) 是 \(C\) 的二进制中 \(0\) 的数量，\(s2\) 是 \(C\) 的二进制中 \(1\) 的数量。

\(x\) 和 \(y\) 可以通过在开头放 \(s\) 个 \(1\) 的方式既不改变异或大小，又能凑到 \(a\) 和 \(b\)。

然后按 \(1\) 的个数列出方程,设 \(x\) 的相同数位中有 \(x'\) 个 \(0\)，不同数位中有 \(y'\) 个 \(0\)。

解这个不定方程即可。

注意要判断 \(x\) 和 \(y\) 是否 \(<2^{60}\)。

（二）

AC 代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,pos[20010],n,s1,s2,s,X[20010],Y[20010],cc;
signed main(){
	cin>>a>>b>>c;
	cc=c;
	while(c>0){
		pos[++n]=c&1;
		c>>=1;
		s1+=pos[n]==0,s2+=pos[n]==1;
	}
	if((s2+b-a)%2==1){
		cout<<-1;
		return 0;
	}
	int y=(s2+b-a)/2,x;
	int p=2*s1+s2-b-a;
	if(abs(p)%2==1){
		cout<<-1;
		return 0;
	}
	if(p>0)s=0,x=p/2;
	else x=0,s=(-p)/2;
	if(n+s>60){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(pos[i]==0){
			if(x)X[i]=0,x--;
			else X[i]=1;
			Y[i]=X[i];
		}
		else{
			if(y)X[i]=0,y--;
			else X[i]=1;
			Y[i]=X[i]^1;
		}
	}
	for(int i=1;i<=s;i++)n++,X[n]=Y[n]=1;
	int sx=0,sy=0;
	p=1;
	for(int i=1;i<=n;i++){
		sx+=X[i]*p,sy+=Y[i]*p;
		p*=2;
	}
	int ssx=sx,ssy=sy;
	while(ssx>0){
		a-=ssx&1;
		ssx>>=1;
	}
	while(ssy>0){
		b-=ssy&1;
		ssy>>=1;
	}
	if(n<=60&&a==0&&b==0&&(sx^sy)==cc)cout<<sx<<" "<<sy<<endl;
	else cout<<-1;
	return 0;
}