[ARC208C] Mod of XOR 题解
linjunye
·
·
题解
我尽量讲得易懂一点。
首先很显然，x\oplus C 是可能的一个解，我们可以提前 check。
有位运算，有取模，这很难转换，于是我们尝试从“异或之后的结果与原数的关系”下手。
我们开始分类讨论。
第一种：n 最高位大于等于 C 最高位。
这时候你发现 n\oplus C 一定小于 2n。如果 n\oplus C<n，那么 n=x\oplus C 就是可能的解；否则我们可以把 (n\oplus C)\bmod n 变成 (n\oplus C)-n，然后我们再把 n\oplus C-n 变成 n+C-2(n
\text{ and }C))-n 即 C-2(n
\text{ and }C)。因此我们可以得到 n\ \text{and}\ C=\frac{C-x}{2}。这个时候，如果 C<x 或者 C-x 为奇数或者 \frac{C-x}{2} 不是 C 的二进制子集，n 就无解。
否则，为了确保 n 最高位大于等于 C 最高位，我们可以构造 n=\frac{C-x}{2}+2^W。这里 W 取到 30 以上应该都行，我取到了 50。
接下来我们讨论 n 最高位低于 C 最高位。
这时候你发现 n\oplus C 一定大于等于 2n，有什么用吗？好像没用。
似乎没有进展了。我们换一种方向思考：我们能不能根据上面讨论出来的无解情况，继续尝试构造有解情况？
首先是 C<x。显然 n<C，所以 (n\oplus C)\bmod n 必定比 n 小，所以当 C<x 时必定无解。
好像没什么思路了……唉，我们能不能暴力算同余方程？
为什么上面没有想到呢？因为上面的性质太直接了，导致我们直接错过了往同余去想的情况。但是没关系，因为上面的推导在这时候会发挥一些作用的。
我们列出式子：(n\oplus C)\bmod n=x。
然后根据上面的想法，把 n\oplus C 拆掉：(n+C-2(n
\text{ and }C))\bmod n=x。
把 n 去掉：(C-2(n
\text{ and }C))\bmod n=x。
移项：(n
\text{ and }C)\bmod n=\frac{C-x}{2}。
你发现它还是需要满足上面的关系：$C-x$ 是奇数，$\frac{C-x}{2}$ 是 $C$ 的二进制子集。
所以 $n$ 最高位小于 $C$ 最高位的构造并不能“根据上面分类讨论出来的无解情况，构造有解情况”。
所以只需尝试构造 $n=x\oplus C$ 和 $n=\frac{C-x}{2}+2^W$。
注意构造 $x\oplus C$ 的优先级高于我们所判断的一切。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
const int N=1000010;
int x,c;
bool chk(int n){if(!n)return false;return (n^c)%n==x;}
void solve(){
cin>>c>>x;
if(chk(c^x)){
cout<<(c^x)<<"\n";
return;
}
if(c<x){
cout<<"-1\n";
return;
}
int d=(c-x)/2;
if(chk((1ll<<50)+(d&c))){//这里没有判断子集关系等关系，因为如果满足就一定合法，不满足也不影响它无解。
cout<<(1ll<<50)+(d&c)<<"\n";
return;
}
cout<<"-1\n";
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int Tc=1;
cin>>Tc;
while(Tc--)solve();
return 0;
}
/*
*/
```