【Nowcoder 上海五校赛】1 + 2 = 3?

题目描述

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

(表示按位异或运算)

输入描述:

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

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

输出描述:

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

[示例1]

输入

4
1
2
3
10

输出

1
2
4
18

题解

首先我们可以打表，在数据小的情况下找规律：

在1~100之间找出满足规律的数，并转成二进制

--------------------------------

第1个数     1     1                       // 二进制1位的个数为1
第2个数     2     10                     // 二进制2位的个数为1
第3个数     4     100                   // 二进制3位的个数为2
第4个数     5     101
第5个数     8     1000                 // 二进制4位的个数为3
第6个数     9     1001
第7个数     10   1010
第8个数     16   10000               // 二进制5位的个数为5
第9个数     17   10001
第10个数   18   10010
第11个数   20   10100
第12个数   21   10101
第13个数   32   100000             // 二进制6位的个数为8
第14个数   33   100001
第15个数   34   100010
第16个数   36   100100
第17个数   37   100101
第18个数   40   101000
第19个数   41   101001
第20个数   42   101010
第21个数   64   1000000            // 二进制7位的个数为13
第22个数   65   1000001
第23个数   66   1000010
第24个数   68   1000100
第25个数   69   1000101
第26个数   72   1001000
第27个数   73   1001001
第28个数   74   1001010
第29个数   80   1010000
第30个数   81   1010001
第31个数   82   1010010
第32个数   84   1010100
第33个数   85   1010101

--------------------------------

结果我们发现答案在二进制下其位数是满足斐波那契规律的

 

例：当N等于70时，答案的二进制为：100100010

① 70-1-1-1-2-3-5-8-13-21=15

可知1+1+1+2+3+5+8+13+21=55，即9位二进制（第55个数对应100000000）

② 15-1-1-1-2-3-8=0

可知1+1+1+2+3+5+8=15，即6位二进制（第15个数对应100010）

③ 相加可得100100010，转换为十进制即为290

 

所以得把给定的n拆成几个斐波那契数的和，并标记一下每次用到第几个斐波那契数，每次num加上1<<(pos-1)即可。

得好好学学左移运算符啦！！！！

#include<bits/stdc++.h> 
using namespace std;
int main()
{
    long long a[65],num,n,d;
    int t,i;
     
    a[0]=a[1]=a[2]=1;
    for (i=3;i<60;i++)
        a[i]=a[i-1]+a[i-2];
     
    cin>>t;
    while(t--)
    {
        cin>>n;
        num=0;
        while(n)
        {
            i=0;
            while(n>=a[i])
            {
                n-=a[i];
                i++; 
            }
            d=1;
            num+=(d<<(i-1));
        }
        cout<<num<<endl;
    }
    return 0;
}