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.Exampleinput
3 2 3 5
output
3 1 7
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$.
Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); vector<int> a = {1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401}; map<int, int> mp; int ptr = 0; for (int i = 3; i <= (1 << 25) - 1; i = i * 2 + 1) { /* int mx = 0; for (int j = 1; j < i; j++) { mx = max(mx, __gcd(i & j, i ^ j)); } cerr << mx << ",";*/ mp[i] = a[ptr++]; } int tt; cin >> tt; while (tt--) { int n; cin >> n; if (mp.count(n)) { cout << mp[n] << '\n'; } else { int x = 1; while (x < n) { x = x * 2 + 1; } cout << x << '\n'; } } return 0; }