分数: 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 否则。
约束
- 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 等也将被接受。