思路和官方题解应该差不多，但我自认为还是比他讲的清楚一点，其实就是一个对暴力法的上界优化
思路讲解
有一点是肯定的，d<=floor(p/2) d 才可能被 p 整除
当然这题肯定还是和位运算相关嘛，所以我们更关心的其实是 d 的二进制最高位和 p 是不一样的
然后我大概猜到是怎么一回事了。
只需要对暴力代码进行一些小小的改动就行
1
| for(ll y=1;y<=min(m,change(x));++y) {
|
把循环上界改成 min(m,change(x)) 就行
那这个 change(x) 是啥那？
1
2
3
4
5
6
7
8
9
| 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代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #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……）
暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #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;
}
|