Meaningless Operations (Codeforces 1110C)
Tags: Math, number theory

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) 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)}.$$$$$$Here $$$\oplus$$$ denotes the bitwise XOR operation, and $$$\&$$$ denotes the bitwise AND operation.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.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). 

Input: 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. 

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

Note: 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$$$.

Sample Inputs:
3
2
3
5

Sample Outputs:
3
1
7

Solution (Python):
import math
for _ in range(int(input())):
    n = int(input())
    x = math.floor(math.log(n, 2))
    if n == 2 ** (x + 1) - 1:
        print(n // [n, n, n, 3, n, 3, n, 3, 7, 3, 23, 3, n, 3, 7, 3, n, 3, n, 3, 7, 3, 47, 3, 31][x])
    else:
        print(2 ** (x + 1) - 1)

Solution (Python):
for s in [*open(0)][1:]:
    k = (1 << len(bin((n := int(s)))) - 2) - 1
    if n ^ k:
        print(k)
        continue
    for i in range(2, 50):
        if i < k and k % i == 0:
            print(k // i)
            break
    else:
        print(1)

Solution (Python):
from math import gcd
n = int(input())
mp = {}
mp[3] = 1
mp[7] = 1
mp[15] = 5
mp[31] = 1
mp[63] = 21
mp[127] = 1
mp[255] = 85
mp[511] = 73
mp[1023] = 341
mp[2047] = 89
mp[4095] = 1365
mp[8191] = 1
mp[16383] = 5461
mp[32767] = 4681
mp[65535] = 21845
mp[131071] = 1
mp[262143] = 87381
mp[524287] = 1
mp[1048575] = 349525
mp[2097151] = 299593
mp[4194303] = 1398101
mp[8388607] = 178481
mp[16777215] = 5592405
mp[33554431] = 1082401
for i in range(n):
    x = int(input())
    l = x.bit_length()
    if x in mp:
        print(mp[x])
    else:
        print((1 << l) - 1, end='\n')