CF1110C Meaningless Operations

最大公约数和位运算之间会有什么联系吗？现在是解答这个问题的时候了。 给定一个正整数 $a$。你需要从 $1$ 到 $a-1$（包含 $1$ 和 $a-1$）中选择一个整数 $b$，使得整数 $a \oplus b$ 与 $a \& b$ 的最大公约数尽可能大。换句话说，你需要计算如下函数： $$ f(a) = \max_{0 < b < a} \gcd(a \oplus b, a \& b) $$ 其中，$\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)，$\&$ 表示[按位与运算](https://en.wikipedia.org/wiki/Bitwise_operation#AND)。 两个整数 $x$ 和 $y$ 的最大公约数是能够整除 $x$ 和 $y$ 的最大整数 $g$。 现在给定 $q$ 个整数 $a_1, a_2, \ldots, a_q$，对于每个整数，计算在最优选择 $b$ 时，最大公约数的最大可能值。

第一行包含一个整数 $q$（$1 \leq q \leq 10^3$），表示需要计算答案的整数个数。 接下来有 $q$ 行，每行一个整数，分别为 $a_1, a_2, \ldots, a_q$（$2 \leq a_i \leq 2^{25} - 1$），表示需要计算答案的整数。

对于每个整数，按照输入顺序输出答案，每行一个。

对于第一个整数，最优选择是 $b = 1$，此时 $a \oplus b = 3$，$a \& b = 0$，$3$ 和 $0$ 的最大公约数是 $3$。 对于第二个整数，一种最优选择是 $b = 2$，此时 $a \oplus b = 1$，$a \& b = 2$，$1$ 和 $2$ 的最大公约数是 $1$。 对于第三个整数，最优选择是 $b = 2$，此时 $a \oplus b = 7$，$a \& b = 0$，$7$ 和 $0$ 的最大公约数是 $7$。 由 ChatGPT 4.1 翻译