← 返回题目列表

Codeforces · 2039/C1

C1. Shohag 喜欢 XOR(简单版)

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

这是问题的简单版本。两个版本之间的差异以粗体突出显示。只有解决了两个版本的问题后,您才能进行黑客攻击。

Shohag 有两个整数 $$$x$$$ 和 $$$m$$$。帮助他计算整数 $$$1 \le y \le m$$$ 的数量,使得 $$$\mathbf{x \neq y}$$$ 和 $$$x \oplus y$$$ 是 $$$x$$$ 和/或 $$$y$$$ 的约数 $$$^{\text{∗}}$$$。这里 $$$\oplus$$$ 是按位异或运算符。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含两个空格分隔的整数 $$$x$$$ 和 $$$m$$$ ($$$1 \le x \le 10^6$$$, $$$1 \le m \le 10^{18}$$$)。

保证所有测试用例的 $$$x$$$ 总和不超过 $$$10^7$$$。

输出

对于每个测试用例,打印一个整数 - 合适的 $$$y$$$ 的数量。

示例

输入 #1

5
6 9
5 7
2 3
6 4
4 1

输出 #1

3
2
1
1
0

注意

在第一个测试用例中,对于 $$$x = 6$$$,从 $$$1$$$ 到 $$$m = 9$$$ 的整数中有 $$$3$$$ 的 $$$3$$$ 有效值,它们是 $$$4$$$、$$$5$$$ 和 $$$7$$$。

- $$$y = 4$$$ 有效,因为 $$$x \oplus y = 6 \oplus 4 = 2$$$ 和 $$$2$$$ 是 $$$x = 6$$$ 和 $$$y = 4$$$ 的除数。
- $$$y = 5$$$ 有效,因为 $$$x \oplus y = 6 \oplus 5 = 3$$$ 且 $$$3$$$ 是 $$$x = 6$$$ 的除数。
- $$$y = 7$$$ 有效,因为 $$$x \oplus y = 6 \oplus 7 = 1$$$ 和 $$$1$$$ 是 $$$x = 6$$$ 和 $$$y = 7$$$ 的除数。

在第二个测试用例中,对于$$$x = 5$$$,从$$$1$$$到$$$m = 7$$$的整数中有$$$2$$$有效值$$$y$$$,它们是$$$4$$$和$$$6$$$。

- $$$y = 4$$$ 有效,因为 $$$x \oplus y = 5 \oplus 4 = 1$$$ 和 $$$1$$$ 是 $$$x = 5$$$ 和 $$$y = 4$$$ 的除数。
- $$$y = 6$$$ 有效,因为 $$$x \oplus y = 5 \oplus 6 = 3$$$ 且 $$$3$$$ 是 $$$y = 6$$$ 的除数。