[ARC208C] Mod of XOR 题解

我尽量讲得易懂一点。

首先很显然，

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

我们已经判断掉了。

你发现它还是需要满足上面的关系：

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;
}
/*

*/

[ARC208C] Mod of XOR 题解

文章操作

相关推荐

评论

[ARC208C] Mod of XOR 题解