← 返回题目列表

AtCoder · arc208_c

C. 异或模

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你正整数 C 和 X 小于 2^{30}.

判断是否存在正整数 n 满足以下所有条件,如果存在,请找到一个这样的 n.

  • 1\le n < 2^{60}
  • (n \oplus C) \bmod n=X

在这里, n \oplus C 表示按位 \mathrm{XOR} of n 和 C.

你被给予 T 测试用例,解决每个用例。

什么是按位 \mathrm{XOR}?

按位 \mathrm{XOR} 非负整数 X 和 Y, X \oplus Y,定义如下:

  • 当 X \oplus Y 以二进制形式写入,其中的数字 2^k 地点(k \geq 0)是 1 如果恰好是其中的数字之一 2^k 地点 X 和 Y 写成二进制是 1,和 0 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 1\le T\le 2\times 10^5
  • 1\le C,X < 2^{30}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

C X

输出

按顺序输出每个测试用例的答案,以换行符分隔。

对于每个测试用例,如果不存在 n 满足所有条件,打印 -1.

否则,打印 n 满足所有条件。

如果有多个 n 满足所有条件,其中任何一个都将被接受。


样本输入 1

3
10 6
2 3
777 153

示例输出 1

7
-1
208

考虑第一个测试用例。

n=7 满足所有条件,因为 (n\oplus C) \bmod n = (7 \oplus 10) \bmod 7 = 13\bmod 7 = 6=X。因此,印刷 第一行的 7 将被接受。

除此之外,打印 n=12,18,19 等也将被接受。