分数: 500 点
问题陈述
给你两个正整数 N 和 K。正整数 X 被称为 兼容 N 如果满足以下条件:
- 按位异或 X 和 N 等于以下情况下的余数: X 除以 N.
判断是否至少存在 K 这样的整数 X 兼容 N。如果它们确实存在,请找到 K- 第一个最小的此类整数。
你被给予 T 测试用例;解决它们中的每一个。
关于异或
非负整数的按位异或 A 和 B,表示 A\ \mathrm{XOR}\ B,定义如下:
- 在二进制表示中 A\ \mathrm{XOR}\ B,中的数字 2^k 地点(用于 k \geq 0) 是 1 当且仅当恰好之一 A 和 B 有一个 1 在 2^k 放置在其二进制表示中。否则的话,就是 0.
约束
- 1 \le T \le 2\times 10^5
- 1 \le N,K \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
在这里, \text{case}_i 表示 i- 第一个测试用例。
每个测试用例均按以下格式给出:
N K
输出
对于每个测试用例,如果至少存在 K 兼容的正整数 N,打印 K- 第一个最小的此类整数。否则,打印 -1.
示例输入 1
4 2 1 2 2 1 7 20250126 191
示例输出 1
2 3 -1 20381694
考虑这种情况 N=2.
- 当 X=1, X\ \mathrm{XOR}\ N = 3 和其余的 X 除以 N is 1。因此, 1 不兼容 N.
- 当 X=2, X\ \mathrm{XOR}\ N = 0 和其余的 X 除以 N is 0。因此, 2 兼容 N.
- 当 X=3, X\ \mathrm{XOR}\ N = 1 和其余的 X 除以 N is 1。因此, 3 兼容 N.
因此,在与 2,最小的是 2 第二小的是 3。因此,答案为 \text{case}_1 is 2 以及答案 \text{case}_2 is 3.