链接：https://ac.nowcoder.com/acm/problem/15979 来源：牛客网

题目描述 小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：

f[0]=0 f[1]=1; f[i]=f[i/2]+f[i%2];(i>=2)

现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n'] = f[n] = f[x/2]+f[x%2] = f[x]...（n'<n<x） 他们的值都相等，这里需要你输出最小的那个n'的值)(n<10^18) 思路：求f(n)的值很容易，直接递推便可以，难点是求值第一次出现的位置；观察可以分析出，题目中的递归条件其实是将十进制数转换为二进制的过程，即如果除二余1，则将f（n）结果加一，所以最后的结果便是这个十进制数变为2进制后有几个1； 源码：#include<bits/stdc++.h> using namespace std; using ll=long long; ll f(ll n) { if(n==0)return 0; else if(n==1)return 1; else return f(n/2)+f(n%2); } int main() { int t; cin>>t; while(t>0) { t--; ll n;cin>>n; ll i=f(n); while(n!=0&&n%2==0) n=n/2; cout<<i<<' '<<(((ll)1<<i)-1)<<endl; } return 0; }