https://codeforces.com/contest/1110/problem/C

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 aa. You want to choose some integer bb from 11 to a−1a−1 inclusive in such a way that the greatest common divisor (GCD) of integers a⊕ba⊕b and a&ba&b is as large as possible. In other words, you'd like to compute the following function:

 

f(a)=max0<b<agcd(a⊕b,a&b).f(a)=max0<b<agcd(a⊕b,a&b).

Here ⊕⊕ denotes the bitwise XOR operation, and && denotes the bitwise AND operation.

The greatest common divisor of two integers xx and yy is the largest integer gg such that both xx and yy are divided by gg without remainder.

You are given qq integers a1,a2,…,aqa1,a2,…,aq. For each of these integers compute the largest possible value of the greatest common divisor (when bb is chosen optimally).

题意：对于给定的a，求f(a)=max{gcd(a^b,a&b)},b∈[1,a-1]

打表找规律不难做。

正解：若a不是2^x-1，则显然b为a按位取反时答案最大，例如：a=1100101，b=0011010，a&b=0，a^b=1111111，f(a)=1111111

若a是2^x-1,gcd(a^b,a&b)=gcd(2^x-1-b,b)=gcd(b,2^x-1),枚举2^x-1的因数就行了，在sqrt(a)时间求出。