zd的小窝
0%

P8845小卡和质数

发表于

题意简述

询问第 $x$ 个质数异或上第 $y$ 个质数是否为 $1$。

解决方案

下面我们约定 $x<y$。

显然两数异或起来为 $1$，则两数奇偶性不同，而所有质数中只有第一个质数 $2$，为偶数，所以首先 $x$ 为 $1$ 。

然后我们发现除了 $2,3$ ，其他的质数都大于 $4$，也就是会对二进制下第二位以上产生贡献，显然不再为 $1$。

于是得出结论：只有 $x=1,y=2$ 时才满足条件，其他情况下都不满足。

代码实现

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
/*
	Author:zd
	Status:WA on pretest 2
*/

#include <bits/stdc++.h>
using namespace std;
signed main(){
	int _;
	cin>>_;
	while(_--){
		int x,y;
		cin>>x>>y;
		if(x>y)swap(x,y);
		if(x==1&&y==2){
			puts("Yes");
		}
		else puts("No");
	}
	return 0;
}


//数组开大了没有 ？开不开 long long ？多测清空了吗 ？