上海高校金马五校赛 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个满足题中等式的正整数，并换行。

输入例子:

4

1

2

3

10

输出例子:

1

2

4

18

-->

示例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[];

void init(){

    a[] = a[] = ;

    for(int i =  ; i <=  ; i++){

    a[i] = a[i-] + a[i-];

    }

}int main()

{

     init();

    int t;

    for(scanf("%d",&t);t--;){

        int s[]={};

        LL n,sum = ;cin>>n;

        while(n > ){

            int ard = upper_bound(a+,a+,n)-a-;

            n -= a[ard];

            sum += 1LL <<(ard-);

        }

        cout<<sum<<endl;

    }

}