题解：CF2039C2 Shohag Loves XOR (Hard Version)
LiJoQiao
·
·
题解
仅以此题纪念我赛时会但是写挂了一万年的 C2。
题意翻译
求 $y\in \left[1,m\right]$ 中满足 $x\bigoplus y \mid x$ 或 $x\bigoplus y \mid y$ 的 $y$ 的数量。
### sol
分类讨论两种情况。
当 $x\bigoplus y \mid x$ 时，令 $x\bigoplus y= i\times x$，$y=(i\times x)\bigoplus x$，得 $y\in \left[(i-1)\times x,(i+1)\times x\right]$。
令 $j=\left\lfloor\dfrac{m}{x}\right\rfloor$，得 $j\times x\le m<(j+1)\times x$。
因此当 $i+1\le j$ 时，$y$ 一定满足 $y\le m$，由异或运算后非负的性质可得 $y\ge 1$ 或 $y=0$，我们需要排除后者 $y=0$，即 $i=1$ 时，因此我们把 $i\in[0,j-1],i\neq1$ 中 $i$ 的数量统计起来。
$i=j$ 或 $i=j+1$ 时由值域得可能满足答案，需要特判。
当 $x\bigoplus y \mid y$ 时，若 $y<x$，我们可以用枚举的方式统计。
当 $y\ge x$ 时，令 $x\bigoplus y=i\times y\in\left[y-x,x+y\right]$，$x+y\le2\times y$ 当且仅当 $y=x$ 时等号成立。
令 $i=0$，得 $x=y$。
令 $i=1$，得 $x=0$，舍去。
令 $i=2$，得 $2\times y\le x+y$，所以 $y=x$，不符合题意，舍去。
至此我们已处理完所有情况，但是我们可能有重复的情况，我们需要去重。
前者中 $i\in[0,j+1],i\neq 1$，$i=0$ 时 $y=x$。 其他情况下由 $y\in \left[(i-1)\times x,(i+1)\times x\right]$ 得 $y\ge x$，但 $y=x$ 时 $i=0$ 故 $y>x$。
后者由前面的讨论得 $y\le x$，两者的交为 $y=x$，不要重复统计此情况即可。
空间复杂度为 $O(1)$。
时间复杂度的开销主要在枚举，复杂度为 $O(\sum x)$。
代码如下。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x;
ll m,ans;
template<typename T>
T read(){
T f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return f*x;
}
namespace sol{
void solve(){
ans=0;
x=read<int>();m=read<ll>();
ll j=m/x;
ans+=j;
if(1<=((j*x)^x)&&((j*x)^x)<=m)++ans;
if(1<=(((j+1)*x)^x)&&(((j+1)*x)^x)<=m)++ans;
if(j-1>=1)--ans;//排除y=0的情况
for(int y=1;y<=min((ll)(x-1),m);++y){
if((x^y)%y==0){
++ans;
}
}
printf("%lld\n",ans);
}
}
int main(){
int T=read<int>();
while(T--)sol::solve();
return 0;
}
```