【ACWing】4982. 进制

题目地址：

https://www.acwing.com/problem/content/4985/

给定两个整数a , b a, ba,b。请你计算，在区间[ a , b ] [a,b][a,b]范围内有多少个整数满足其二进制表示恰好有一个0 00。不考虑前导0 00。例如，当a = 5 , , b = 10 a=5,, b=10a=5,,b=10时，[ 5 , 10 ] [5,10][5,10]范围内的所有整数及其二进制表示如下：
5 10 = 10 1 2 5_{10}=101_2510​=1012​
6 10 = 11 0 2 6_{10}=110_2610​=1102​
7 10 = 11 1 2 7_{10}=111_2710​=1112​
8 10 = 100 0 2 8_{10}=1000_2810​=10002​
9 10 = 100 1 2 9_{10}=1001_2910​=10012​
1 0 10 = 101 0 2 10_{10}=1010_21010​=10102​
可以看出，只有5 55和6 66满足二进制表示恰好有一个0 00。

输入格式：
共一行，两个整数a , b a, ba,b。

输出格式：
输出一个整数，表示满足条件的整数数量。

数据范围：
仅6 66个测试点满足1 ≤ a ≤ b ≤ 1 0 4 1 \le a \le b \le 10^41≤a≤b≤104。
所有测试点满足1 ≤ a ≤ b ≤ 1 0 18 1 \le a \le b \le 10^{18}1≤a≤b≤1018。

暴力枚举一下所有的满足条件的数字即可。代码如下：

#include<iostream>usingnamespacestd;usingll=longlong;intmain(){ll a,b;scanf("%lld%lld",&a,&b);staticautof=[&](ll x){intres=0;for(inti=1;i<=63;i++)for(intj=0;j<=i-1;j++){ll n=(1<<i+1)-1-(1<<j);if(n<=x)res++;}returnres;};printf("%d\n",f(b)-f(a-1));}

时空复杂度O ( 1 ) O(1)O(1)。