← 返回题目列表

Codeforces · 2190/F

F. 异或积

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

对于非负整数 $$$x, y$$$ 和正整数 $$$k$$$,令 $$$S(x, y, k)$$$ 为所有 $$$0 \le i, j \lt k$$$ 的值集 $$$(x + i) \oplus (y + j)$$$。形式上: $$S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j \lt k \}$$ 其中 $$$\oplus$$$ 表示按位异或运算。

将 $$$f(x, k)$$$ 定义为 $$$S(x, y, k)$$$ 在所有非负整数 $$$y$$$ 上的最大大小(即 $$$y \ge 0$$$)。

给定整数 $$$x$$$ 和 $$$k$$$。计算 $$$f(x, k)$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

接下来的 $$$t$$$ 行包含两个整数 $$$x$$$ 和 $$$k$$$ ($$$1 \le x, k \le 10^{17}$$$)。

输出

对于每个测试用例,输出一个整数 - $$$f(x, k)$$$ 的值。

示例

输入
复制

6
67 1
7 3
100 12
1 1043
1526 1043
88946092640567295 100000000000000000

输出
复制

1
7
32
3128
4167
398158383604301822

注意

在第一个示例中,由于 $$$k=1$$$,集合 $$$S$$$ 将始终只包含一个元素,而不管 $$$y$$$ 如何。例如,如果我们选择 $$$y = 69$$$,则 $$$S(67, 69, 1) = \{67 \oplus 69\} = \{6\}$$$,因此 $$$|S(x, y, k)| = 1$$$。

在第二个示例中,我们有 $$$x = 7$$$ 和 $$$k = 3$$$。最佳选择是 $$$y = 8$$$。 $$$(x + i) \oplus (y + j)$$$ 的值为: $$[7 \oplus 8, 7 \oplus 9, 7 \oplus 10, 8 \oplus 8, 8 \oplus 9, 8 \oplus 10, 9 \oplus 8, 9 \oplus 9, 9 \oplus 10]$$ 简化为 $$$[15, 14, 13, 0, 1, 2, 1, 0, 3]$$$。不同值的集合为 $$$S(7, 8, 3) = \{0, 1, 2, 3, 13, 14, 15\}$$$,因此大小为 $$$7$$$。可以证明,没有其他 $$$y$$$ 产生更大的大小。然而,$$$y$$$ 的选择很重要;例如,如果您选择 $$$y = 22$$$,您将得到 $$$S(7, 22, 3) = \{16, 17, 30, 31\}$$$,大小为 $$$4$$$,这是次优的。

在第六个例子中,经过无数次计算,我们得出最优的$$$y$$$是$$$278\,302\,368\,699\,121\,665$$$,答案是$$$398\,158\,383\,604\,301\,822$$$。证明留给读者作为一个简单的练习。