C. Interesting Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya and his friend, robot Petya++, like to solve exciting math problems.One day Petya++ came up with the numbers nn and xx and wrote the following equality on the
board:
n & (n+1) & … & m=x,n & (n+1) & … & m=x
where && denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal mm (m≥nm≥n) that the equality on the board holds. Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.Can you solve this difficult problem?
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤2000). The description of the test cases follows.The only line of each test case contains two integers n, x (0≤n,x≤10^18).
Output
For every test case, output the smallest possible value of mm such that equality holds.If the equality does not hold for any m, print −1 instead.We can show that if the required m exists, it does not exceed 5⋅10^18.
Example
input
5
10 8
10 10
10 42
20 16
1000000000000000000 0
output
12
10
-1
24
1152921504606846976
Note
In the first example, 10 & 11=10, but 10 & 11 & 12=8, so the answer is 12.
In the second example, 10=10, so the answer is 10.
In the third example, we can see that the required m does not exist, so we have to print −1.
思路：
我们可以
按位考虑。如果
n 在这一位上是 0 ， x 在这一位上是 0
选取任何的 m 都可行。
n 在这一位上是 0 ， x 在这一位上是 1
不可能实现。
n 在这一位上是 1 ， x 在这一位上是 0
必须等到某一个在这一位为 0 的数出现，才能满足要求。
设这个数最小为 k ，则可行域与 [k,+∞] 取交集。
n 在这一位上是 1 ， x 在这一位上是 1
m 必须在某一个在这一位为 0 的数出现之前，才能满足要求。
设这个数最小为 k ，则可行域与 [n,k) 取交集。
最后，如果可行域不为空，输出最小元素。时间复杂度是 Θ(logmax(n,x))
代码：
1 #include<bits/stdc++.h>
2 #define N 70
3 using namespace std;
4 typedef long long ll;
5
6 void solve()
7 {
8 ll n,x;
9 scanf("%lld%lld",&n,&x);
10 bitset<64> bn(n),bx(x);
11 ll l=n,r=5e18;
12 for(int i=63;i>=0;i--)
13 {
14 if(bn[i]==0 && bx[i]==1)
15 {
16 puts("-1");
17 return;
18 }
19 if(bn[i]==0 && bx[i]==0) continue;
20 if(bn[i]==1 && bx[i]==0)
21 {
22 l=max(l,((n/(1ll<<i))+1)*(1ll<<i));
23 //二进制 1010 * 10 = 10100
24 //一个数乘 100...00 相当于左移相应的位数
25 //一个数整除 100...00 相当于把这个1右边的所有位数变成0
26 }
27 else{
28 r=min(r,((n/(1ll<<i))+1)*(1ll<<i)-1);
29 }
30 }
31
32 if(l<=r) printf("%lld\n",l);
33 else puts("-1");
34
35 return ;
36 }
37
38 int main()
39 {
40 int _;
41 cin>>_;
42 while(_--) solve();
43 return 0;
44 }
Noted by DanRan02
2023.1.11
