Codeforces Round 843 C题

题意：本题是给定n和x，试求是否存在m>=n，满足n & (n+1) & … & m=x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve()
{
	ll n, x; cin >> n >> x;

	bitset<64> b1(n), b2(x);

	ll l = n, r = 5e18, fuck = n;
	for (int i = 63; i >= 0; i--)	//要注意bitset是逆序输出的
	{
		if (b1[i] == 0 && b2[i] == 1)
		{
			cout << -1 << '\n';
			return;
		}
		if (b1[i] == 0 && b2[i] == 0) continue;
		if (b1[i] == 1 && b2[i] == 0)
		{
			// 可行域是第一次该位出现0的时候
			l = max(l, ((n / (1ll << i)) + 1) * (1ll << i));
		}
		else
		{
			// 可行域是这一位为0的数出现之前
			r = min(r, ((n / (1ll << i)) + 1) * (1ll << i) - 1);
			// cout << r << endl;
		}
	}
	if (l <= r) cout << l << '\n';	//左端点大于等于右端点
	else cout << -1 << '\n';
}
int main()
{
	int t;
	cin >> t;
	while (t--)
		solve();
	system("pause");
	return 0;
}