A16568. Xor Product
编程题
NOI/NOI+/CTSC
知识点
题目描述
对于非负整数 $x, y$ 和正整数 $k$，定义 $S(x, y, k)$ 为所有 $(x + i) \oplus (y + j)$ 的集合，其中 $0 \le i, j < k$。形式化地：
$$ S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j < k \} $$
这里 $\oplus$ 表示按位异或运算。
定义 $f(x, k)$ 为对于所有非负整数 $y$（即 $y \ge 0$），集合 $S(x, y, k)$ 的最大可能大小。
给定整数 $x$ 和 $k$，计算 $f(x, k)$。
$$ S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j < k \} $$
这里 $\oplus$ 表示按位异或运算。
定义 $f(x, k)$ 为对于所有非负整数 $y$（即 $y \ge 0$），集合 $S(x, y, k)$ 的最大可能大小。
给定整数 $x$ 和 $k$，计算 $f(x, k)$。
输入格式
本题包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。
接下来的 $t$ 行，每行包含两个整数 $x$ 和 $k$（$1 \le x, k \le 10^{17}$）。
接下来的 $t$ 行，每行包含两个整数 $x$ 和 $k$（$1 \le x, k \le 10^{17}$）。
输出格式
对于每个测试用例，输出一个整数，即 $f(x, k)$ 的值。
输入输出样例
输入 #1
6 67 1 7 3 100 12 1 1043 1526 1043 88946092640567295 100000000000000000
输出 #1
1 7 32 3128 4167 398158383604301822
说明/提示
在第一个样例中，由于 $k=1$，无论 $y$ 取何值，集合 $S$ 总是恰好包含一个元素。例如，若选取 $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$。证明过程留作读者的一个简单练习。
在第二个样例中，$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$。证明过程留作读者的一个简单练习。