题目描述

小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

做法

求f(n)就是正常递归，但是要注意，这题卡常数了，就是f(n%2)要直接求出来，不能再递归下去。

接下来的问题就是怎么求它值相同的最小项呢，我们发现，f(n)的含义就是十进制n转为二进制时1的个数。那么最小项对应的二进制就是f(n)个1，而最小项对应的十进制怎么求，就是2的f(n)次方-1，也就是1左移f(n)位-1。

#include<bits/stdc++.h>
using namespace std;
int t;
int f(long long n){if(n==0) return 0;if(n==1) return 1;if (n%2==0) return f(n/2);else return f(n/2)+1;
}
int main(){scanf("%d",&t);while(t--){long long k;scanf("%lld",&k);int ans=f(k);cout<<ans<<" ";long long res=(1LL << ans)-1;//1要强制转换为long long，不然移动后超过32位会爆cout<<res<<endl;}
}