前言
这道题十分诈骗，比赛的时候以为是根据二进制除法原理，解同余方程，然后考试时候就没做出来QAQ。
这篇题解是构造解法，至于官方题解是啥我也不知道，看这官方题解的性质十分诡异。 （其实就是我英语不好看不懂）
题面
题目描述
You are given three integers $ a $ , $ b $ , and $ d $ . Your task is to find any integer $ x $ which satisfies all of the following conditions, or determine that no such integers exist:
- $ 0 \le x \lt 2^{60} $ ;
- $ a|x $ is divisible by $ d $ ;
- $ b|x $ is divisible by $ d $ .
Here, $ | $ denotes the bitwise OR operation.
题面翻译
给定正整数 \(a,b,d\)，求一个正整数 \(x\) 使得 \(d\mid(a\operatorname{or}x)\) 且 \(d\mid(b\operatorname{or}x)\)，其中 \(\operatorname{or}\) 表示按位或运算。
数据范围
多组输入
\[1\le T\le 10^4,1\le a,b,d\le 2^{30} \]思路
由于 \(x\) 必须满足
- $ a|x $ is divisible by $ d $ ;
- $ b|x $ is divisible by $ d $ .
所以显然的，如果当前存在解，那么一定存在一个 \(x\) 使得 \(x\) 包含 \(a|b\) 且 \(x\) 可以被 \(d\) 整除。即
- \(x|(a|b)=x\) 且 \(x\) is divisible by $ d $
考虑无解情况
因为 \(x\) 必须被 \(d\) 整除 且 \(x|(a|b)=x\)，所以如果 \(a|b\) 的最低位如果比 \(d\) 的最低位还低，那么 \(x\) 则无法被 \(d\) 整除，该情况无解。
考虑如何让 \(x\) 被 \(d\) 整除
首先我们让 \(x=0\) 设 \(c=a|b\) ，进行这么一个操作：
-
每次找到他们二进制最低位 \(i\)，使得 \(x\) 的 \(i\) 位为 \(0\) 且 \(c\) 的 \(i\) 位为 \(1\)。
-
然后将 \(d\) 移动一定位数使得 \(d\) 的最低为 \(1\) 与 \(x\) 的 \(i\) 位对其，然后 \(x=x+d\)。
显然的，二进制高位的操作无法堆低位产生影响，所以，这样进行若干次操作后，就可以得到一个满足以条件的 \(x\)。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
int a,b,d;
signed main(){
cin>>T;
while(T--){
cin>>a>>b>>d;
int c=(a|b);
int cnt=0;
int x=0;
bool flag=false;
while(!(d&1)){//为了方便以下操作，我们将d的最低位1与0位对其
if(c&1){//a|b的最低位1比d的最低位1还低，满足无解情况
puts("-1");
flag=true;
break;
}
c>>=1;d>>=1;
++cnt;//记录对其所右移的次数，输出答案时需要移回去
}
if(flag) continue;
for(int i=0;i<=30&&c;++i){
if((c&1)&&!((x>>i)&1)){//找到他们二进制最低位 i，使得 x 的 i 位为 0 且 c 的 i 位为 1。
x+=(d<<i);//将d的最低为1与i位对其
}
c>>=1;
}
cout<<(x<<cnt)<<endl;
}
return 0;
}