CF1748D ConstructOR 题解
As_Snow
·
·
题解
upd on 2025.8.15: 感谢 @dangbowen1008 在工单中指出问题，谢罪。
可能更好的食用体验
既然题目中用到了位运算，那我们就用二进制来解决这道题。
1.判无解
观察 3\,4\,6 这个样例，我们将其分解二进制：
\begin{aligned}
(3)_{10} &= (11)_2 \\
(4)_{10} &= (100)_2\\
(6)_{10} &= (110)_2\\
\end{aligned}
我们设 \operatorname{lowbit}(x) 表示 x 最末尾的 1 在第几位，那么我们可以发现一条性质：\operatorname{lowbit}(d)\le\operatorname{lowbit}(a\operatorname{ or }b)。如果不满足，那么一定无解。
2.构造 x
我们来分析样例中的第一组数据：
\begin{aligned}
a &= 1100\\
b &= 100111\\
d &= 101\\
\end{aligned}
\begin{aligned}
1100&\\
100111&\\
\text{---------------}\\
101&\\
101\;\;&\\
101\;\;\;\;\;\;\;\;\;\\
\text{---------------}\\
10101111
\end{aligned}
我们可以发现 x 有若干个 d 相加得到，并且 (a\operatorname{or}x )=x,(b\operatorname{or}x )=x,所以一定满足 d\,|\,(a\operatorname{or}x) 且 d\,|\,(a\operatorname{or}x)。
### Code
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,b,d,k,x;
void solve(){
cin>>a>>b>>d;
k=x=0;//k表示lowbit(d)
while((d>>k&1)^1)k++;
for(int i=0;i<30;i++)
if( ((a|b)>>i&1) && (x>>i&1)==0 )
if(i<k)return void(puts("-1"));//判无解
else x+=(d<<i-k);
cout<<x<<endl;
}
signed main(){
cin>>T;
while(T--)solve();
return 0;
}
```
P.s. 应为构造方式比较特殊，所以输出会和样例输出不一样，~~不要像我一样傻傻的为此去调了二十分钟~~。
#### 样例输出
```
175
14
-1
-1
2
27
64446
143838208856161791
```