链接：https://ac.nowcoder.com/acm/contest/21763/1002
来源：牛客网

题目描述

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

输入描述: 

输入第一行一个t
随后t行，每行一个数n，代表你需要求数列的第n项，和相应的n'
(t<4*10^5)

输出描述: 

输出每行两个正整数
f[n]和n'，以空格分隔
示例1

输入 

2
0
1

输出 

0 0
1 1
本题给出了递推公式，明显使用递归去求解。但坑的地方在于不能直接按照题目中所给的递推式进行递归（会超时）。从题目中看出i%2完全可以直接手动算出。
题目中f(n)的含义是求某个数二进制下有多少个1，那么最早出现的就是前面全都是1的情况。使用左移后减一的操作可以直接求出。
要注意：(1<<sum)-1是不对的，因为在这里默认1是int类型，需要强转成long long类型，(1ll<<sum)-1 
#include <bits/stdc++.h> typedef long long ll;

using namespace std;

ll calc(ll n) {
    if (n==0) return 0;
    if (n==1) return 1;
    return calc(n/2)+n%2;
}

int main() {
    ll t, n;
    cin>>t;
    while (t--) {
        scanf("%lld", &n);
        ll sum = calc(n);
        printf("%lld %lld\n", sum, (1LL<<sum)-1);
    }
    
    return 0;
}