题目描述
小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’,以空格分隔
AC
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
/*
n=17;
f[10001]=f[1000]+1=f[100]+1+0=f[10]+1+0+0=f[1]+1+0+0+0=10001
n=18;
f[10010]=f[1001]+0=f[100]+0+1=f[10]+0+1+0....
则f[n]的值为其二进制各个位数的和
如何找到最小的n
从小到大添加1即可
如n=5,则为11111
*/
int func(ll n)
{
if(n==0)return 0;
else if(n==1)return 1;
else
{
if(n%2==0)return func(n/2);
else return func(n/2)+1;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
int res=func(n);
if(res==0)cout<<0<<" "<<0<<endl;
else if(res==1)cout<<1<<" "<<1<<endl;
else{
ll t = 1;
int p=res;
while(p--)
{
t*=2;
}
cout<<res<<" "<<t-1<<endl;
}
}
return 0;
}
你好,我的兄弟
兄弟好,我洗了澡还能变成蓝色呢