题目描述
给定两个整数 $a,b$。
请你计算,在 $[a,b]$ 范围内有多少个整数满足其二进制表示恰好有一个 0。
不考虑前导 $0$。
例如,当 $a=5,b=10$ 时,$[5,10]$ 范围内的所有整数及其二进制表示如下:
$5_{10}=101_2,6_{10}=110_2,7_{10}=111_2,8_{10}=1000_2,9_{10}=1001_2,10_{10}=1010_2$
可以看出,只有 $5$ 和 $6$ 满足二进制表示恰好有一个 $0$。
输入格式
共一行,两个整数 $a,b$。
输出格式
一个整数,表示满足条件的整数数量。
数据范围
前 $6$ 个测试点满足 $1≤a≤b≤10^4$。
所有测试点满足 $1≤a≤b≤10^{18}。$
样例
输入样例1:
5 10
输出样例1:
2
输入样例2:
2015 2015
输出样例2:
1
输入样例3:
100 105
输出样例3:
0
算法1
(暴力枚举) $O({\log ^ 3 n})$
先枚举前i
位为前导0,第j
位为0,算出10进制数,暴力即可,具体看代码
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
LL a, b;
LL solve(LL x)
{
LL res = 0;
for (int i = 0; i < 64; i ++ ) // 0 ~ i - 1
for (int j = i + 1; j < 64; j ++ ) //第j位为0
{
LL sum = 0, t = 1;
for (int k = 63; k >= i; k -- ) //秦九韶算法
{
if (k != j) sum += t;
t *= 2;
}
if (sum <= x) res ++ ;
}
return res;
}
int main()
{
cin >> a >> b;
cout << solve(b) - solve(a - 1); //类似数位DP
}
更短的做法
大佬,可以帮我看一下我的方法哪里有问题吗