CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)——C1. Shohag Loves XOR (Easy Version) · znzryb
思路和官方题解应该差不多，但我自认为还是比他讲的清楚一点，其实就是一个对暴力法的上界优化
## 思路讲解
有一点是肯定的，$d<=floor(p/2)$ $d$ 才可能被 $p$ 整除
当然这题肯定还是和位运算相关嘛，所以我们更关心的其实是 $d$ 的二进制最高位和 $p$ 是不一样的
然后我大概猜到是怎么一回事了。
只需要对暴力代码进行一些小小的改动就行
```cpp
for(ll y=1;y<=min(m,change(x));++y) {
```
把循环上界改成 $min(m,change(x) )$ 就行
那这个 $change(x)$ 是啥那？
```cpp
inline ll change(ll x) {
ll res=1;
while (true) {
if(x==0)
return res*2;
x/=2;
res*=2;
}
}
```
其实很简单，就是 $2**(ceil(log2(x)))$ 的意思（**是次方的意思），只不过写了个循环而已 。
然后我们来说我大概猜到什么了
$y$ 可以很大，相对来说 $x$ 就比较小，那么当 $y$ 很大的时候，$d=$$x$^$y$ ( ^是异或的意思) 的高位完全是跟着 $y$ 走的，但这样的 $d$ 首先不可能被 $x$ 整除，其次也不可被y整除（我们前面看了，$d$ 的高位是不能和 $y$ 一样的）
当然这个 $y$ 要多大才会这样那？其实只要大到 $y$ 的最高位异或时不受 $x$ 影响就行了，也就是
$y>=2**(ceil(log2(x)))$
其实异或还真和加法很像，一个高位的数异或低位的数几乎不会有什么影响。
## AC代码
[](https://codeforces.com/contest/2039/submission/293086942)
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=static_cast<int>(2e5)+15;
int T;
inline ll change(ll x) {
ll res=1;
while (true) {
if(x==0)
return res*2;
x/=2;
res*=2;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
ll x,m;
cin>>x>>m;
ll ans=0;
for(ll y=1;y<=min(m,change(x));++y) {
ll div=x^y;
if(div==0)
continue;
if(x%div==0 || y%div==0) {
++ans;
}
}
cout<<ans<<endl;
}
return 0;
}
```
## 心路历程（WA，TLE，MLE……）
暴力
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=static_cast<int>(2e5)+15;
int T;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
ll x,m;
cin>>x>>m;
ll ans=0;
for(ll y=1;y<=m;++y) {
ll div=x^y;
if(div==0)
continue;
if(x%div==0 || y%div==0) {
++ans;
}
}
cout<<ans<<endl;
}
return 0;
}
```