CF1775C.Interesting Sequence

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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)\ \&\ \dots\ \&\ m = x,$$ where &\& denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal mm (m≥nm \ge 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?

佩佳和他的朋友——机器人佩佳++,喜欢解决有趣的数学问题。

有一天,佩佳++想出了两个数 nn 和 xx,并在黑板上写下了如下等式:

n & (n+1) & … & m=x,n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,

其中 &\& 表示按位与运算。接着,他建议他的朋友佩佳找出满足该等式的最小 mm(要求 m≥nm \ge n)。

不幸的是,佩佳无法心算解决这个问题,于是决定求助于计算机。他迅速编写了一个程序,并找到了答案。

你能否解决这个难题?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤20001 \le t \le 2000). The description of the test cases follows.

The only line of each test case contains two integers nn, xx (0≤n,x≤10180\le n, x \le 10^{18}).

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤20001 \le t \le 2000)。随后是各测试用例的描述。

每个测试用例仅有一行,包含两个整数 nn、xx(0≤n,x≤10180\le n, x \le 10^{18})。

输出格式

For every test case, output the smallest possible value of mm such that equality holds.

If the equality does not hold for any mm, print −1-1 instead.

We can show that if the required mm exists, it does not exceed 5⋅10185 \cdot 10^{18}.

对于每个测试用例,输出使得等式成立的最小可能的 mm 值。

如果不存在使等式成立的 mm,则输出 −1-1。

可以证明:若所求的 mm 存在,则其值不超过 5⋅10185 \cdot 10^{18}。

输入输出样例

  • 输入#1

    5
    10 8
    10 10
    10 42
    20 16
    1000000000000000000 0

    输出#1

    12
    10
    -1
    24
    1152921504606846976

说明/提示

In the first example, 10 & 11=1010\ \&\ 11 = 10, but 10 & 11 & 12=810\ \&\ 11\ \&\ 12 = 8, so the answer is 1212.

In the second example, 10=1010 = 10, so the answer is 1010.

In the third example, we can see that the required mm does not exist, so we have to print −1-1.

在第一个例子中,10 & 11=1010\ \&\ 11 = 10,但 10 & 11 & 12=810\ \&\ 11\ \&\ 12 = 8,因此答案为 1212。

在第二个例子中,10=1010 = 10,因此答案为 1010。

在第三个例子中,我们可以看出所要求的 mm 不存在,因此需输出 −1-1。

输入解题思路,AI测评打分。不知道怎么写?

首页