题解：CF2039C2 Shohag Loves XOR (Hard Version)

仅以此题纪念我赛时会但是写挂了一万年的 C2。

题意翻译

t

组数据。
求

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;
}

题解：CF2039C2 Shohag Loves XOR (Hard Version)

文章操作

题意翻译

sol

相关推荐

评论

题解：CF2039C2 Shohag Loves XOR (Hard Version)