305917: CF1110C. Meaningless Operations

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Meaningless Operations

题意翻译

定义函数 $f(a)$ 的值为: $$f(a)=\max_{0<b<a}\gcd(a\oplus b,a\ \&\ b)$$ 给出 $q$ 个询问,每个询问为一个整数 $a_i$。你需要对于每个询问,求出 $f(a_i)$ 的值。 数据范围:$1\le q\le 10^3$,$2\le a_i\le 2^{25}-1$

题目描述

Can the greatest common divisor and bitwise operations have anything in common? It is time to answer this question. Suppose you are given a positive integer $ a $ . You want to choose some integer $ b $ from $ 1 $ to $ a - 1 $ inclusive in such a way that the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ a \oplus b $ and $ a \> \& \> b $ is as large as possible. In other words, you'd like to compute the following function: $ $f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}. $ $ </p><p>Here $ \\oplus $ denotes the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#XOR">bitwise XOR operation</a>, and $ \\& $ denotes the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>.</p><p>The greatest common divisor of two integers $ x $ and $ y $ is the largest integer $ g $ such that both $ x $ and $ y $ are divided by $ g $ without remainder.</p><p>You are given $ q $ integers $ a\_1, a\_2, \\ldots, a\_q $ . For each of these integers compute the largest possible value of the greatest common divisor (when $ b$ is chosen optimally).

输入输出格式

输入格式


The first line contains an integer $ q $ ( $ 1 \le q \le 10^3 $ ) — the number of integers you need to compute the answer for. After that $ q $ integers are given, one per line: $ a_1, a_2, \ldots, a_q $ ( $ 2 \le a_i \le 2^{25} - 1 $ ) — the integers you need to compute the answer for.

输出格式


For each integer, print the answer in the same order as the integers are given in input.

输入输出样例

输入样例 #1

3
2
3
5

输出样例 #1

3
1
7

说明

For the first integer the optimal choice is $ b = 1 $ , then $ a \oplus b = 3 $ , $ a \> \& \> b = 0 $ , and the greatest common divisor of $ 3 $ and $ 0 $ is $ 3 $ . For the second integer one optimal choice is $ b = 2 $ , then $ a \oplus b = 1 $ , $ a \> \& \> b = 2 $ , and the greatest common divisor of $ 1 $ and $ 2 $ is $ 1 $ . For the third integer the optimal choice is $ b = 2 $ , then $ a \oplus b = 7 $ , $ a \> \& \> b = 0 $ , and the greatest common divisor of $ 7 $ and $ 0 $ is $ 7 $ .

Input

题意翻译

定义函数 $f(a)$ 的值为: $$f(a)=\max_{0<b<a}\gcd(a\oplus b,a\ \&\ b)$$ 给出 $q$ 个询问,每个询问为一个整数 $a_i$。你需要对于每个询问,求出 $f(a_i)$ 的值。 数据范围:$1\le q\le 10^3$,$2\le a_i\le 2^{25}-1$

加入题单

上一题 下一题 算法标签: