1+2=3?(奇怪的斐波那契规律题)

2018-04-15

1+2=3？

题目

输入一个T，接下来T行，每行一个N，输出满足 x异或2x== 3x 的第N个数字。

T<=100,N<=1e12

思路

打了表，整数数列百科全书中找到符合规律的数列，观察二进制形式后发现：

斐波那契数列：

1 2 3 5 8 13 21 34 55 ……

题中若N=60，则60= 55 + 5 （第9项+第4项）

则第60个满足条件的数为：1(9)00001(4)000 = 264 (4、9号位数为1，其他都是0)

由于1e12小于斐波那契的第59项，故开一个59大的数组，里面存斐波那契数，然后对于每一个N寻找最少的组成它的斐波那契数，找到他是第x项，那么ans+2^x即可。

（问题是我的代码怎么这么丑= =）

看！代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    vector<long long>fei; //算斐波那契 1 2 3 5这样的
    fei.push_back(1);fei.push_back(2);
    while(fei[fei.size()-1]<(1e12+5)) fei.push_back(fei[fei.size()-1]+fei[fei.size()-2]);
 
    while(t--)
    {
        long long n,temp;
        scanf("%lld",&n);
        temp=n;
        long long weishu[100],x=1,ans=0;
        for(int i=0;i<60;i++)
            weishu[i]=x,x*=2; //计算2的i次
      
        for(int i=57;i>=0;i--)
            if(temp>=fei[i]) //找能组成他的斐波那契数，直接算
                temp-=fei[i],ans+=weishu[i];
      
        printf("%lld\n",ans);
    }
    return 0;
}