题解：CF2039C2 Shohag Loves XOR (Hard Version)
_xm_
·
·
题解
非常好的题目，十分考验对位运算本质的理解。
文章开头先列一下等式：（下文按位与以 \land 表示，下文或位与以 \lor 表示)
\begin{align}
0 \le &a \land b \le \min(a,b) \\
\max(a,b) \le &a \lor b \le a+ b \\
|a-b| \le &a \oplus b \le a+b \\
&a+b=a \oplus b+2(a \land b)
\end{align}
Problem
CF2039C1
CF2039C2
Easy Version Solution
给定 x,m，求有多少 y 满足 y \in [1,m],x \neq y 且 x \oplus y 是 x 或 y 的因子。
根据题意可直接推出 $x \oplus y < x$ 且 $x \oplus y < y$。
由式 4 可得：
$$
\begin{aligned}
x + y - 2(x \land y) < x \Rightarrow y < 2(x \land y) \le 2\min(x, y) \\
x + y - 2(x \land y) < y \Rightarrow x < 2(x \land y) \le 2\min(x, y)
\end{aligned}
$$
$x$ 的上下界我们不用管，但是注意到 $y < 2\min(x, y)$ 对我们十分关键，这说明 $y$ 不会很大，有上界 $2x$，直接枚举即可。
# Hard Version Solution
给定 $x,m$，求有多少 $y$ 满足 $y \in [1,m]$ 且 $x \oplus y$ 是 $x$ 或 $y$ 的倍数。
考虑分别计算 $x \oplus y$ 是 $x$ 的倍数，$x \oplus y$ 是 $y$ 的倍数，最后再想办法减去重复计算的部分。
### 情况 1：$x \oplus y$ 是 $x$ 的倍数
$x \oplus y=kx \Rightarrow |x - y| \le kx\le x+y(k\ge2)$ 结合 $y \in[1,m]$ 得到 $k\le \lfloor \frac{m+x}{x} \rfloor$。
同理可得 $k\le \lfloor \frac{m-x}{x} \rfloor$，$k$ 只有 $O(1)$ 个，枚举即可。
### 情况 2：$x \oplus y$ 是 $y$ 的倍数
$x \oplus y=ky \Rightarrow ky\le x+y(k\ge2)$ 得到 $(k-1)y \le x$。
$y$ 有上界 $x$，枚举即可。
### 情况 3：$x \oplus y$ 既是 $x$ 的倍数也是 $y$ 的倍数
情况 3 是被情况 1、2 包含的，且为处理前两个情况我们枚举了所有满足约束的 $(x,y)$，所以可以在处理情况 1 时或处理情况 2 时同时处理情况 3。
# 总结
位运算可以计算上下界，熟练掌握后可以像四则运算一样推导。此外猜测 **答案 / 某枚举量** 比较小也是 guessforces 老生常谈的思路之一。