Codeforces 1748 D

这场D还是很有趣的，值得探讨。

首先\(a|x,b|x\)是两个数，不相同时不太好做，所以我们能否找到一个\(x\)，满足\(a|x=b|x\)并且都是\(d\)的倍数呢？

然后我们让\(d\)特殊一些——我们先解决\(d\)是奇数的问题。

只要\(x\)包含\(a,b\)中所有为\(1\)的位，并且是\(d\)的倍数就可以了，也就是\(x\&(a|b)=(a|b)\)并且\(x\equiv 0\mod d\)。

那么若\((a|b)\)的第\(i\)位为\(1\)，我们可以让\(x+=2^i\times d\)，这样\(x\)是\(d\)的倍数，并且由于\(d\)的最后一位为\(1\)（\(d\)是奇数），可以保证\(x\)的第\(i\)位也是\(1\)，并且不改变第\(i\)位之前的数字。

程序实现就是下面这样子的：

for(ll i=0;i<30;i++) {
    if(((a|b)&(1ll<<i))>=1) {
	if((x&(1ll<<i))==0) {
		x+=(1ll<<i)*d;
	}
    }
}

那么\(d\)是偶数呢？此时\(d\)的有一系列后缀\(0\)。如果\((a|b)\)在这段内有\(1\)，那么一定无解；否则我们可以先去除掉这些后缀\(0\)，到最后输出答案时加上即可。

可以发现，\(x\)是不超过\(2^{30}\times d\)的，故满足题中\(x\leq 2^{60}\)的条件。

时间复杂度为\(O(T\log n)\)。

完整代码：

#include<bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl

using ll=long long;

void solve() {
	ll a,b,d;
	scanf("%lld%lld%lld",&a,&b,&d);
	ll shift=0,res=0;
	while(!(d&1ll)) d>>=1ll,shift++;
	for(ll i=0;i<shift;i++) {
		if((a&(1ll<<i))||(b&(1ll<<i))) {
			printf("-1\n");
			return;
		}
	}
	a>>=shift; b>>=shift;
	for(ll i=0;i<30;i++) {
		if(((a|b)&(1ll<<i))>=1) {
			if((res&(1ll<<i))==0) {
				res+=(1ll<<i)*d;
			}
		}
	}
	printf("%lld\n",res<<shift);
}

int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		solve();
	}
	return 0;
}