← 返回题目列表

AtCoder · arc191_b

B. 异或 = MOD

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

分数: 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.
例如, 3\ \mathrm{XOR}\ 5 = 6 (二进制: 011\ \mathrm{XOR}\ 101 = 110).

约束

  • 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.