题解: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;
}