← 返回题目列表

Codeforces · 1110/C

C. 无意义的操作

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

最大公约数和按位运算有什么共同点吗?是时候回答这个问题了。

假设给你一个正整数 $$$a$$$。您想要从 $$$1$$$ 到 $$$a - 1$$$ 之间选择一些整数 $$$b$$$,其中整数 $$$a \oplus b$$$ 和 $$$a \> \& \> b$$$ 的最大公约数 (GCD) 尽可能大。换句话说,您想要计算以下函数:

$$$$$$f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.$$$$$$

这里$$$\oplus$$$表示按位异或运算,$$$\&$$$表示按位与运算。

两个整数 $$$x$$$ 和 $$$y$$$ 的最大公约数是最大整数 $$$g$$$,使得 $$$x$$$ 和 $$$y$$$ 都除以 $$$g$$$ 而没有余数。

给你 $$$q$$$ 整数 $$$a_1, a_2, \ldots, a_q$$$。对于每个整数,计算最大公约数的最大可能值(当 $$$b$$$ 被最佳选择时)。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^3$$$) — 您需要计算答案的整数个数。

之后给出 $$$q$$$ 整数,每行一个:$$$a_1, a_2, \ldots, a_q$$$ ($$$2 \le a_i \le 2^{25} - 1$$$) - 您需要计算答案的整数。

输出

对于每个整数,按照输入中给出的整数相同的顺序打印答案。

示例

输入 #1

3
2
3
5

输出 #1

3
1
7

注意

对于第一个整数,最佳选择是 $$$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$$$。