XTUOJ-1307 Beautiful Number

题目描述

如果一个数的二进制中只有1个0，那么我们称这样的数是“美丽数”，比如510=1012。 现在给你一个区间$$[a,b]\(1 \le a \le b \le 10 ^ {18}\)$$，求区间内有多少个“美丽数”。

输入

第一行是一个整数K，表示样例的个数。 每个样例是两个整数a和b。

输出

每行输出一个样例的结果。

样例输入

3
1 2
2 5
1 1000000000000000000

样例输出

1
2
1712

思路

只要求出从 1 到某个数之间的所有的美丽数个数，然后再 ans[b] - ans[a] 就行了。

但首先得承认，看到题目和数据范围时我是懵逼的。

不过看到最大输入（1000000000000000000）也不过输出（1712）时，我就明白了这题一定有着巧妙的方法，比如离线打表，可惜我太菜了，递推公式我推不出来。

那退而求其次，如何求从 1 到某个数之间的所有的美丽数个数呢？

一个数的二进制中只有 1 个 0，我们可以考虑使用位运算。

先推几个数：

• 1D = 1B，不是
• 2D = 10B，是
• 3D = 11B，不是
• 4D = 100B，不是
• 5D = 101B，是
• 6D = 110B，是

可以通过肉眼和数学证明（n = x 2 + 1 或 n = x 2）发现，如此能取遍所有的数。

而想要成为美丽数，x 必须也是一个美丽数，或者 x 满足二进制下全是 1 。

这样子，就给我们暴搜提供了剪枝的可能性。

只要计算 x << 1 | 1 （x 为美丽数）和 x << 1 （x 全是1）就行了。

其中， x << 1 对同个数只能用一次，因为第二次末尾将有两个 0 。

然后无脑深搜就行了。

func(int *x){
    return *x += 1;
}
func(&x);