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