埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 F

1 + 2 = 3?
链接：https://www.nowcoder.com/acm/contest/91/F
来源：牛客网

题目描述
小Y在研究数字的时候，发现了一个神奇的等式方程，他屈指算了一下有很多正整数x满足这个等式，比如1和2，现在问题来了，他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。

(表示按位异或运算)

输入描述:
第一行是一个正整数，表示查询次数。

接着有T行，每行有一个正整数，表示小Y的查询。

输出描述:
对于每一个查询N，输出第N个满足题中等式的正整数，并换行。
示例1
输入
4
1
2
3
10
输出
1
2
4
18

题目分析：
这个题由于x+2x=3x 所以我们要异或 刚好是两数的和的，所以我们要找的数的二进制形式中不能有相邻的1，所以我们枚举一下前几种情况

0
1
10
100
101
1000
1001
1010
因此我们可以发现，每个相同位数为一组，每组的个数我们可以通过
f(n)=f(n-1)+f(n-2)来计算得出，再通过求一个前缀和，我们就可以算出第几个数在整个序列中是第几组，这一组我们计算最高为的1的权值，剩下的通过取余到前面去找即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
ll a[maxn];
ll b[maxn];
ll bit[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    a[1]=1;
    a[2]=1;
    a[3]=1;
    bit[1]=1;
    // bit[2]=2;
    for(int i=2; i<=63; i++)
    {
        bit[i]=bit[i-1]*2;
    }
   // cout<<bit[63]<<endl;
    for(int i=4; i<=64; i++)
    {
        a[i]=a[i-1]+a[i-2];
    }
    b[0]=0;
    //cout<<a[64]<<endl;
    for(int i=1; i<=64; i++)
    {
        b[i]=b[i-1]+a[i];
        //cout<<i<<" "<<b[i]<<endl;
    }
    //cout<<b[64]<<endl;
    while(t--)
    {
    ll n;
    scanf("%lld",&n);
    ll ans=0;
    ll index=n;
    while(index)
    {
        int t=upper_bound(b+1,b+64,index)-b;
        //cout<<t<<endl;
        index=index-b[t-1];
        ans+=bit[t-1];
    }
    printf("%lld\n",ans);
    }
    return 0;
}