南昌大学航天杯第二届程序设计竞赛校赛网络同步赛 H小q的数列

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll f[1000010];

ll dfs(ll i)

{

if(f[i]!=-1)

{

return f[i];

}

return f[i/2]+f[i%2];

}

long long read(){

long long res = 0;

int flag = 0;

char ch;

if ((ch = getchar()) == '-'){

flag = 1;

}

else if(ch >= '0' && ch <= '9'){

res = ch - '0';

}

while ((ch = getchar()) >= '0' && ch <= '9'){

res = res * 10 + (ch - '0');

}

//    if(flag)    printf("a[i] = %I64d\n",-res);

//    else printf("a[i] = %I64d\n",res);

return flag ? -res : res;

}

int main()

{

memset(f,-1,sizeof(f));

ios::sync_with_stdio(false);

f[0]=0; f[1]=1;

for(ll i=2;i<=1e6;i++)

{

f[i]=dfs(i);

}

ll t;

t=read();

while(t--)

{

ll n; n=read();

ll count=0;

while(n>1e6)

{

if(n%2!=0)n--,n/=2,count++;

while(n%2==0)n=n/2;

}

ll ans=f[n];

ans+=count;

printf("%lld %lld\n",ans,(ll)pow((ll)2,(ll)ans)-1);

}

return 0;

}