Mining a
Time limit2sMemory limit1024 MB
For each n, find the largest a such that 1/n = 1/(a xor b) + 1/b for some positive integer b.
- Level
Hard9 of 10
- Topics
- Math, Bit manipulation, Number theory, Brute force
- Solved
- No attempts yet
Problem
Blockchain technology is used in many digital currency systems, such as Bitcoin and Ethereum. In this technology, distributed users share a common list of records (called the chain), and a user has the right to add a new record to the chain by solving a mathematical problem. This process is called mining. The i-Taiwan company has developed a new digital currency system, called ICPC (I-taiwan Coins for the Public Currency). In the ICPC system, its mathematical problem for mining is as follows. Given positive integer n, the problem asks one to find the largest integer a such that
1/n = 1/(a⊕b) + 1/b, for some positive integer b
where ⊕ is the bitwise exclusive-or operator. For example, for n = 12, its solution is a = 145. In this case, b = 13 and thus a ⊕ b = 145 ⊕ 13 = 10010001₂ ⊕ 1101₂ = 10011100₂ = 156. Accordingly,
1/(a⊕b) + 1/b = 1/156 + 1/13 = 1/12 = 1/n.
You are an ambitious programmer, and you want to mine a lot of digital coins from this system in a short time. Please write a program to find the largest a for each n in order to earn the rewards from ICPC.
Input
The first line of the input file contains exactly one positive integer T that gives you the number of test cases. In the following T lines, each line corresponds to one test case and specifies the integer n.
Output
For each test case, output the largest number a in one line.
Constraints
- 1 ≤ T ≤ 20
- 0 < n ≤ 10⁷