1.题号:NC15979

2.题目原文:

• 小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)

3.链接：https://ac.nowcoder.com/acm/problem/15979

• 来源：牛客网

4.思路:

• 按照递推公式推导可知，fi的值即为i的二进制表示中1的个数，用递推逆求出fi

5.代码:

using namespace std;
typedef long long ll;
int task(ll x)
{
    if(x==0) return 0;
    if(x==1) return 1;
    return task(x/2)+task(x%2);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll x;cin>>x;
        int k=task(x);
        cout<<k<<' '<<((1LL<<k)-1)<<'\n';
    }
}