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