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;
}

 

全部评论

相关推荐

07-09 15:55
门头沟学院 Java
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务