题解 | #小q的数列#

这题可以找规律，可以列出前几项看看，其实它是和n的二进制大小有关。

用a来表示n的二进制中1的个数，可以看出，f（n）的值与a相等，n'等于2 的a次方-1。

f[0]=0 f[1]=1; f[i]=f[i/2]+f[i%2];(i>=2) 其实这个式子就是不断把二进制的i右移一位，再看一下i是不是奇数（二进制最后一位是不是1），如果是就+1，那么任何数都能化成f[1]+X，X= i的二进制中1的个数 - 1。最早出现的n'就是2的0次方一直加到2的X次方（2的a次方-1），就是n'的二进制全是1，并且1的个数=i的二进制中1的个数。

#include<iostream>
using namespace std;
#define ll long long
 //返回x的二进制中的最后一个1的值，比如100000100，返回100
ll lowbit(ll x){
    return x&(-x);
}
 
 
int main(){
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll res=0;
        while(n) n-=lowbit(n),res++;
        cout<<res<<' ';
        ll x=1;
        while(res--) x*=2; 
        cout<<x-1<<endl;
    }
     
    return 0;
}