上海高校金马五校赛 F题：1 + 2 = 3?

链接：https://www.nowcoder.com/acm/contest/91/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

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

(表示按位异或运算)

输入描述:

第一行是一个正整数，表示查询次数。

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

输出描述:

对于每一个查询N，输出第N个满足题中等式的正整数，并换行。

示例1

输入

4
1
2
3
10

输出

1
2
4
18


题意：求第k个正整数，使得 (k^(2*k))== 3*k
题解：正解是数位dp。。我队找规律过掉的。。
　　  先暴力跑小数据转换成2进制后发现规律：二进制下 1位数的个数是1个，2位数的个数是1个，3位数的个数是2个，4位数的个数是3个....
　　  满足斐波那契数列。然后又发现，在二进制下，如果位数大于3，记位数位m位，那么前两位肯定是10，后面的重复前面m-2位。当然需要补前置0
　　　到此可以发现是个递推的过程。即把给定的k拆成几个斐波那契数的和，然后标记一下是第几个斐波那契数，sum加上1<<(pos-1)即可。
     需要打个斐波那契的表，60位就够了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL a[61];
void init(){ 
    a[0] = a[1] = 1;   
    for(int i = 2 ; i <= 60 ; i++){        
    a[i] = a[i-1] + a[i-2];
    }
}int main()
{
     init();
    int t;
    for(scanf("%d",&t);t--;){
        int s[100]={};
        LL n,sum = 0;cin>>n;
        while(n > 0){
            int ard = upper_bound(a+1,a+60,n)-a-1;
            n -= a[ard];
            sum += 1LL <<(ard-1);
        }
        cout<<sum<<endl;    
    }
}