CF1979B.XOR Sequences

给定两个不同的非负整数 $x$ 和 $y$。考虑两个无限序列 $a_1, a_2, a_3, \ldots$ 和 $b_1, b_2, b_3, \ldots$，其中

• $a_n = n \oplus x$；
• $b_n = n \oplus y$。

这里，$x \oplus y$ 表示整数 $x$ 和 $y$ 的按位异或操作。

例如，当 $x = 6$ 时，序列 $a$ 的前 $8$ 个元素为：$[7, 4, 5, 2, 3, 0, 1, 14, \ldots]$。注意，元素的下标从 $1$ 开始。

你的任务是求出序列 $a$ 和 $b$ 的最长公共子段的长度。换句话说，找到最大的正整数 $m$，使得存在某些 $i, j \ge 1$，满足 $a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$。

$^\dagger$ 序列 $p$ 的一个子段是指 $p_l, p_{l+1}, \ldots, p_r$，其中 $1 \le l \le r$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。接下来的每组测试用例包含一行，包含两个整数 $x$ 和 $y$（$0 \le x, y \le 10^9, x \neq y$）——表示序列的参数。

对于每组测试用例，输出一个整数，表示最长公共子段的长度。

在第一个测试用例中，序列 $a$ 和 $b$ 的前 $7$ 个元素如下：

$a = [1, 2, 3, 4, 5, 6, 7, \ldots]$

$b = [0, 3, 2, 5, 4, 7, 6, \ldots]$

可以证明不存在正整数 $k$ 使得序列 $[k, k + 1]$ 在 $b$ 中作为子段出现。因此答案为 $1$。

在第三个测试用例中，序列 $a$ 和 $b$ 的前 $20$ 个元素如下：

$a = [56, 59, 58, 61, 60, 63, 62, 49, 48, 51, 50, 53, 52, 55, 54, \textbf{41, 40, 43, 42}, 45, \ldots]$

$b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \ldots]$

可以证明，最长的公共子段之一是 $[41, 40, 43, 42]$，长度为 $4$。

由 ChatGPT 4.1 翻译