题解：B4357 [GESP202506 二级] 幂和数
题意
给定正整数 \(l\) 和 \(r\)，求 \([l,r]\) 中有多少个数可被表示成 \(2^x + 2^y(x,y\) 为非负整数\()\)。
数据范围与约定
对于所有测试点，保证 \(1 \le l \le r \le 10^4\)。
题解
\(1.\) 暴力求解
暴力枚举 \([l,r]\) 之间的数，再枚举 \(x\) 和 \(y\)，如果这个数可以被表示为幂和数，就将答案 \(+1\)。
Code
时间复杂度 \(O(n)\)，其中 \(n=r-l+1\)，因为 \(x\) 和 \(y\) 的枚举都是常数（\(14 \times 14 = 196\)）。
void Solve(void)
{int l,r;cin>>l>>r;int ans=0;for(int i=l;i<=r;i++){bool flag=false;for(int x=0;x<=14;x++){for(int y=0;y<=14;y++){if(pow(2,x)+pow(2,y)==i)flag=true;}}if(flag)ans++;}cout<<ans<<endl;
}
\(2.\) 位运算角度
分类讨论：
-
当 \(x \neq y\) 时，\(2^x+2^y\)，因为 \(2^x\) 的二进制位在第 \(x\) 位有 \(1\)，其余全为 \(0\)。所以 \(2^x+2^y\) 的二进制有两位是 \(1\)，其余为 \(0\)。
-
当 \(x=y\) 时，\(2^x+2^y=2^{x+1}\)，所以在 \(x+1\) 位有一个 \(1\)，其余全部为 \(0\)。
\(\therefore\)，当这个数是幂和数是时，它的二进制位只能有 \(\le 2\) 的 \(1\)，特别的，当这个数为 \(1\) 时，虽然满足条件，但不是幂和数，因为最小的幂和数时 \(2^0+2^0=2\)，所以不能从 \(1\)，开始判断，只需要取 \(max\{2,l\}\) 即可。
Code
void Solve(void)
{int l,r;cin>>l>>r;int ans=0;for(int i=max(l,2);i<=r;i++){if(__builtin_popcount(i)<=2)ans++;}cout<<ans<<endl;
}