给出$[A, B]$,求出$[A, B]$内任意数Or起来能得到多少不同的值
又是神仙题,考试的时候最怕这种题了qwq
设A,B二进制分解后第一个不同的位为i,那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位)
考虑剩下的数形成的新的A和B能生成那些数
首先$B-A+1$这些数一定是能生成的
再考虑这些数or起来能得到哪些数
为了方便讨论,把AB分成两个集合
第一个是$S1 = [A, 2^r)$,另一个是$S2 = [2^r, B]$
S1内能生成的数有$[A, 2^r - 1]$
S2内能生成的数有$[2^r, 2^r + 2^{p+1} - 1]$
其中$p$表示B二进制分解后r位置往后下一个1的位置
两个集合Or起来能生成的数有$[A + 2^r, 2^{r+1} - 1]$
最后一个边界我自己没有想出来,其实归纳证明一下是显然的
首先是最高位r,包含该位的元素一定可以通过2^r or S1得到
r - 1往后的都可以由S2得到
然后对AB二进制拆分后判断一下上面说的边界条件即可
#include<cstdio>
#include<iostream>
#include<cstring>
#define LL long long
#define int long long
using namespace std;
const int MAXN = 2001;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL A, B;
int a[MAXN], b[MAXN], N, M;
int Get(int x, int *a) {
int mx = 0;
for(int i = 0; i <= 60; i++) {
if(x & (1ll << i)) mx = i;
a[i] = (bool)(x & (1ll << i));
}
return mx;
}
main() {
A = read(); B = read();
if(A == B) {puts("1"); return 0;}
N = Get(A, a);
M = Get(B, b);
//for(int i = 0; i <= M; i++)
// printf("%d", b[i]);
int r = 0, p = 0;
for(int i = M; i >= 0; i--)
if(a[i] != b[i]) {r = i; break;}
for(int i = r -1; i >= 0; i--)
if(b[i]) {p = i; break;}
//printf("%d %d\n", r, p);
A = 0; B = 0;
for(int i = 0; i <= r; i++) {
if(a[i]) A += (1ll << i);
if(b[i]) B += (1ll << i);
}
int al = A, ar = (1ll << r) + (1ll << (p + 1)) - 1;
int ll = A + (1ll << r), rr = (1ll << (r + 1)) - 1;
if(ar < ll) cout << ar - al + 1 + rr - ll + 1;
else cout << rr - al + 1;
return 0;
}