自动搬运

查看原文

来自洛谷，原作者为

	VitrelosTia What you want, What you do ?

搬运于2025-08-24 22:43:02，当前版本为作者最后更新于2022-11-09 17:20:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题链：P8845 [传智杯 #4 初赛] 小卡和质数

题意

给你 $x$ 和 $y$，问第 $x$ 个质数和第 $y$ 个质数的异或值是否为 $1$。

思路

怎么样的两个数异或值为 $1$ 呢？显然是二进制下只有末尾不同的数，要满足这个条件，需要两数奇偶性不同（思考这个条件是因为考虑到质数特殊的奇偶性质），则两个质数为一奇一偶。

偶数中只有 $2$ 是质数，而易知在其它质数中，只有 $3$ 和 $2$ 的异或值为 $1$。最终得到：两个质数只能是 $3$ 和 $2$。

upd(2025.4.1)：为什么只有 $3$ 呢，因为 $(10)_2=2$，而如果另一个数二进制下有多于 $2$ 位，那前面的位异或出来就已经大于 $1$ 了。然后应该就可以理解了吧，至于前面”二进制下只有末尾不同的数“也是一样的道理。写这篇题解的时候我可能也不是很知道为什么只有 $3$。

$3$ 是第 $2$ 个质数，$2$ 是第一个质数，则 $x$ 和 $y$ 为 $2$ 和 $1$。注意两数可能调换位置。

code

#include<bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
    cin>>t;
    while(t--){
        cin>>a>>b;
        if((a==2&&b==1)||(a==1&&b==2)) puts("Yes");
        else puts("No");
    }
}