CF2190F Xor Product

对于非负整数 $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)$。

本题包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 接下来的 $t$ 行，每行包含两个整数 $x$ 和 $k$（$1 \le x, k \le 10^{17}$）。

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

在第一个样例中，由于 $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$。证明过程留作读者的一个简单练习。 由 ChatGPT 5 翻译