[AtCoderContest015D]A or...or B Problem

试题描述

Nukes has an integer that can be represented as the bitwise OR of one or more integers between \(A\) and \(B\) (inclusive). How many possible candidates of the value of Nukes's integer there are?

求 \(A\) 和 \(B\) 之间选若干个数按位或起来有多少种可能的值。

输入

The input is given from Standard Input in the following format:

A

B

输出

Print the number of possible candidates of the value of Nukes's integer.

输入示例1

7

9

输出示例1

输入示例2

65

98

输出示例2

输入示例3

271828182845904523

314159265358979323

输出示例3

68833183630578410

数据规模及约定

\(1 \le A \le B < 2^{60}\)

\(A\) and \(B\) are integers.

题解

题目地址

首先，\([A, B]\) 范围内的数肯定是能表示出来的。然后我们考虑一下它能表示出的最小的数和最大的数。

最小的数肯定是 \(A\)。然后我们考虑将 \(A\) 和 \(B\) 分解成二进制的形式，设它们前 \(k\) 位的二进制都相同，那么第 \(k+1\) 位上 \(B\) 的肯定是 \(1\)，\(A\) 的肯定是 \(0\)，那么最大值就很好考虑了。我们现在用 \((XXX...)_2\) 表示前 \(k\) 位相同的二进制，那么 \([A, B]\) 区间可以被拆成 \([A, (XXX...011...)_2]\) 和 \([(XXX...100...)_2, B]\)，下面的数字应该会直观一些：

XXX...0****** = A

XXX...0111111 = C

XXX...1000000 = D

XXX...1001--- = B

上面的例子就假设后面只有 \(7\) 位，其中 * 表示 \(A\) 的后几位，- 表示 \(B\) 的后几位。

那么显然我们可以用 \(C\texttt{ }or\texttt{ }D\) 得到最大值 \(XXX...1111111\)。

除此之外，区间 \([A, C]\) 中每个数都可以和 \(D\) 进行按位或运算得到下面这个范围的所有数：

XXX...1****** = E

XXX...1111111 = F

注意到我们用 \([D, B]\) 内部的所有数按位或起来可以得到这个范围的所有数：

XXX...1000000 = D

XXX...1001111 = G

然后我们发现除此之外，再无其他可以搞出来的数了。考虑只用 \([A, G]\) 中的数，组出来的是 \([A, G]\) 或 \([E, F]\) 的数；只用 \([E, F]\) 的数，只能组出来 \([E, F]\) 中的数；两个区间都用只能组出来 \([E, F]\) 中的数，因为数是越或越大的。

所以最后答案就是 \([A, G] \bigcup [E, F]\) 中的所有数了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

#define LL long long

LL read() {

	LL x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

int main() {

	LL l = read(), orgl = l, r = read(), orgr = r, tr = r, ans;

	for(int i = 59; i >= 0; i--)

		if((l ^ r) >> i & 1) {

			l |= 1ll << i;

			int tmp = i;

			for(tmp--; tmp >= 0; tmp--) tr |= 1ll << tmp;

			for(i--; i >= 0 && !(r >> i & 1); i--) ;

			for(i; i >= 0; i--) r |= 1ll << i;

			break;

		}

	if(r >= l) return printf("%lld\n", tr - orgl + 1), 0;

	ans = r - orgl + 1 + tr - l + 1;

	printf("%lld\n", ans);

	return 0;

}

巴特西

[AtCoderContest015D]A or...or B Problem