第一眼:哇,枚举。
第二眼:哇, L , R ⩽ 1 0 9 L,R\leqslant 10^9 L,R⩽109。
枚举是不可能的了。
这时我们就需要动一下脑子。
分两种情况:
L = R L=R L=R 和 L ≠ R L\not = R L=R。
当 L = R L=R L=R 的时候,直接输出 0
就可以了。
当 L ≠ R L \not = R L=R 的时候:设 x = L ⊕ R x = L \oplus R x=L⊕R,那么答案为最小的 2 k − 1 2^k-1 2k−1 让 2 k − 1 ⩾ x 2^k-1 \geqslant x 2k−1⩾x 也就是 2 k > x 2^k > x 2k>x。
证明如下:
第一步:证明没有例外。
我们想让异或之后二进制下最高位尽量高,我们就先取最大的 R R R,然后再取一个数使得该位尽量为 0 0 0。
如果 L L L 这一位是 1 1 1,我们都知道异或是不进位加法, 1 ⊕ 1 1 \oplus 1 1⊕1 当然等于 0 0 0,不用考虑这一位。找后面的也同理。
如果 L L L 这一位是 0 0 0 符合上述条件,此时答案最高位和 x x x 都相同。而 2 k − 1 2^k-1 2k−1 是最高位相同的最大的数,所以答案一定不超过 2 k − 1 2^k-1 2k−1。
第二步:证明可以取到。
以下称在二进制里表示 2 i 2^i 2i 的那一位叫做第 i i i 位。
因为 x = L ⊕ R x=L \oplus R x=L⊕R,在第 k − 1 k-1 k−1 位为 1 1 1,说明 L ∼ R L \sim R L∼R 之间有一个位置的第 k − 1 k-1 k−1 位发生了变化。而且 L ∼ R L \sim R L∼R 是要一起变化的,每次都要加 1 1 1,意思就是肯定有一个位置从 111 … 1 111 \dots 1 111…1(一共 k − 1 k-1 k−1 个 1 1 1),变成了 100 … 0 100 \dots 0 100…0(一共 k − 1 k-1 k−1 个 0 0 0)。所以这两个数异或起来为 2 k − 1 2^k-1 2k−1。
证明完毕。理论存在,实践,开始!
#include<bits/stdc++.h>
using namespace std;
int l,r;
int main(){cin>>l>>r;r^=l;for(int i=0;;i++){if(1<<i>r){ cout<<(1<<i)-1;//这里不打括号就会CE,别问我怎么知道的。(哭) break;}}return 0;
}
去掉头文件和 namespace 只有 12 12 12 行,太简便了。