ICPC Asia Taipei-Hsinchu Regional 2019 H.Mining a（思维）

Problem Description

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-*** company has developed up a new digital currency system, called the ICPC (I-*** Coins for the Public Currency). In the ICPC system, its mathematical problem for mining is as follows. Given positive integer nn, the problem asks one to find the largest integer aa such that

\dfrac{1}{n}=\dfrac{1}{a\oplus b}+\dfrac{1}{b}n1​=a⊕b1​+b1​, for some positive integer bb

where \oplus⊕ is the bitwise exclusive-or operator. For example, for n = 12n=12, its solution is a = 145a=145. In this case, b = 13b=13 and thus a ⊕ b = 145 ⊕ 13 = 10010001_2 ⊕ 1101_2 = 100111002 = 156a⊕b=145⊕13=100100012​⊕11012​=100111002=156. Accordingly,

\dfrac{1}{a\oplus b}+\dfrac{1}{b}=\dfrac{1}{156}+\dfrac{1}{13}=\dfrac{1}{12}a⊕b1​+b1​=1561​+131​=121​

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 aa for each nn in order to earn the rewards from ICPC.

Input Format

The first line of the input file contains exactly one positive integer TT that gives you the number of test cases. In the following TT lines, each line corresponds to one test case and specifies the integer nn.

Output Format

For each test case, output the largest number aa in one line.

Technical Specification

• 1 ≤ T ≤ 201≤T≤20
• 0 < n ≤ 10^70<n≤107

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

3
6
7
10

样例输出1复制

45
48
101

样例输入2复制

3
1
2
7777777

样例输出2复制

0
5
60493819864864

思路：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 1e3 + 10;

int main()
{
    ll t, n, ans;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld", &n);
        ans = n * (n + 1);
        ans = ans ^ (n + 1);
        cout << ans << endl;
    }
    return 0;
}