思路讲解
我们来对想求的进行一下变换
所以就看 y(即m) 里有几个 x^nx 就行了
至于可以被y整除的 x^y ，那个上题中我们证明了这样的情况不会出现在 y ≥ 2**(ceil(log2(x))+1) 之后（**是python中的次方）
然后我们知道^为不进位加法，故 x^nx ≤ (n+1)*x （不进位加法必然不可能比进位加法大嘛），所以我们先看有多少 nx，再通过一些信息，反推出有多少个 x^nx。
然后开开心心码个程序
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
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
inline ll change(ll x) {
ll res=1;
while (true) {
if(x==0)
return res*2;
x/=2;
res*=2;
}
}
int main()
{
cin>>T;
while (T--) {
ll x,m,ans=0;
cin>>x>>m;
ll xchange=change(x);
ll alreadyRecord=0;
for(ll y=1;y<=min(xchange,m);++y) {
ll d=x^y;
if(d%y==0 || d%x==0) {
++ans;
if(d%x==0)
++alreadyRecord;
}
}
if((x^((m/x)*x))>m) {
ans+=max(0LL,(m/x-alreadyRecord-1));
}else {
ans+=max(0LL,(m/x-alreadyRecord));
}
cout<<ans<<endl;
}
return 0;
}
|
样例都过不了？
不要慌，这是因为有回退现象。
但是会有一些非常讨厌的回退，比如说上图，如果你只判到6，你会觉得6是一个不行的数，但是实际上6是可以的，其由 1^(1*7)=6 得来，同理，4也是这样。
那回退现象最多会跨多少出现那？其实最多出现在后面一个，因为^他最多把之前加上的给完全抵消掉，他不可能起到比 -x 更强的效果，就像他不会起到比 +x 更强的效果一样。
1
2
3
4
|
if( (x^(m/x+1)*x) <= m && (x^(m/x+1)*x)>min(xchange,m) ) {
ans+=1;
}
|
加了以下这个&& 是因为被2 9这个数据卡了，(x^(m/x+1)*x) ≤ min(xchange,m) ++ans相当于重复了，≤min(xchange,m) 的早就被我们统计过了，不用再统计了。
1
| (x^(m/x+1)*x)>min(xchange,m)
|
AC代码
https://codeforces.com/contest/2039/submission/293249612
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
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
inline ll change(ll x) {
ll res=1;
while (true) {
if(x==0)
return res*2;
x/=2;
res*=2;
}
}
int main()
{
cin>>T;
while (T--) {
ll x,m,ans=0;
cin>>x>>m;
ll xchange=change(x);
ll alreadyRecord=0;
for(ll y=1;y<=min(xchange,m);++y) {
ll d=x^y;
if(d%y==0 || d%x==0) {
++ans;
if(d%x==0)
++alreadyRecord;
}
}
if(m>xchange) {
if((x^((m/x)*x))>m) {
ans+=max(0LL,(m/x-alreadyRecord-1));
}else {
ans+=max(0LL,(m/x-alreadyRecord));
}
if( (x^(m/x+1)*x) <= m && (x^(m/x+1)*x)>min(xchange,m) ) {
ans+=1;
}
}
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
int main()
{
cin>>T;
while (T--) {
ll x,m,ans=0;
cin>>x>>m;
for(ll y=1;y<=m;++y) {
ll d=x^y;
if(d%y==0 || d%x==0)
++ans;
}
cout<<ans<<endl;
}
return 0;
}
|
我这个程序老是会多一个，后来发现其实整个思路就有点问题
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
inline ll change(ll x) {
ll res=1;
while (true) {
if(x==0)
return res*2;
x/=2;
res*=2;
}
}
int main()
{
cin>>T;
while (T--) {
ll x,m,ans=0;
cin>>x>>m;
ll xchange=change(x);
for(ll y=1;y<=min(xchange,m);++y) {
ll d=x^y;
if(d%y==0 || d%x==0) {
++ans;
}
}
ans+=max(0LL,(m/x-min(xchange,m)/x));
cout<<ans<<endl;
}
return 0;
}
|