#include<cstdio> using namespace std; typedef long long ll; int t; int fun(ll x) { if(x==0) return 0; if(x==1) return 1; return fun(x/2)+x%2; } int main() { scanf("%d",&t); while(t--) { ll x; scanf("%lld",&x); int ans=fun(x); printf("%d %lld\n",ans,(1ll<<ans)-1); } return 0; }
1.f ( x%2) = x % 2 否则被卡常
2. f ( 7 )=f ( 3 )+1 =f ( 1 ) +1 +1 7=111(2)
x/2 相当于 x<<1
x二进制下最低位若1 则+1
结论 f ( x ) :x二进制表示中1的个数
最早的n‘则构造一个 11111...*f(x) 的数
f ( x) =f ( 1<<f(x) - 1 )
3.注意开浪浪和位运算优先级
链接:https://ac.nowcoder.com/acm/problem/15979
来源:牛客网
题目描述
小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)
输出描述:
输出每行两个正整数示例1
f[n]和n',以空格分隔
输入
复制2 0 1
输出
复制0 0 1 1