非常好的题目，十分考验对位运算本质的理解。
文章开头先列一下等式：（下文按位与以
∧ 表示，下文或位与以
∨ 表示)
- ∧ 是按位与，本质是取交集，所以结果不超过两个数中较小的。
- ∨ 是按位或，本质是并集，因此结果不小于两数中较大的，但不超过它们之和。
- ⊕ 是按位异或，本质是不进位加法，不借位减法。
- 最后一式揭示了：加法 = 不进位加法 + 进位。
Problem
Easy Version Solution
给定
x,m，求有多少
y 满足
y∈[1,m],x=y 且
x⊕y 是
x 或
y 的因子。
∑x≤107 的限制让我们猜想
y 的大小与
x 有关，考虑为什么。
根据题意可直接推出
x⊕y<x 且
x⊕y<y。
由式 4 可得：
x+y−2(x∧y)<x⇒y<2(x∧y)≤2min(x,y)x+y−2(x∧y)<y⇒x<2(x∧y)≤2min(x,y)
x 的上下界我们不用管，但是注意到
y<2min(x,y) 对我们十分关键，这说明
y 不会很大，有上界
2x，直接枚举即可。
Hard Version Solution
给定
x,m，求有多少
y 满足
y∈[1,m] 且
x⊕y 是
x 或
y 的倍数。
考虑分别计算
x⊕y 是
x 的倍数，
x⊕y 是
y 的倍数，最后再想办法减去重复计算的部分。
情况 1：x⊕y 是 x 的倍数
x⊕y=kx⇒∣x−y∣≤kx≤x+y(k≥2) 结合
y∈[1,m] 得到
k≤⌊xm+x⌋。
同理可得
k≤⌊xm−x⌋，
k 只有
O(1) 个，枚举即可。
情况 2：x⊕y 是 y 的倍数
x⊕y=ky⇒ky≤x+y(k≥2) 得到
(k−1)y≤x。
情况 3：x⊕y 既是 x 的倍数也是 y 的倍数
情况 3 是被情况 1、2 包含的，且为处理前两个情况我们枚举了所有满足约束的
(x,y)，所以可以在处理情况 1 时或处理情况 2 时同时处理情况 3。
总结
位运算可以计算上下界，熟练掌握后可以像四则运算一样推导。此外猜测 答案 / 某枚举量 比较小也是 guessforces 老生常谈的思路之一。