自动搬运

查看原文

来自洛谷，原作者为

	Iowa_BattleShip AFO/kel

搬运于2025-08-24 22:03:15，当前版本为作者最后更新于2018-07-16 20:07:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一个不需要$STL$的方法
因为每个因子都很大，所以我们不可能直接乘起来再除~~（这不是废话）~~，而题目保证对于一个数字，其在$b_i$中出现的次数不多于在$a_i$中出现的次数，所以我们很容易想到要把$a$中的数用$b$里的约分掉，而众所周知，$a\land a=0$，于是我们就可以考虑利用异或来约分，主要细节看代码说吧。

#include<cstdio>
using namespace std;
typedef long long ll;
ll re()//快读
{
	ll x=0;
	char c=getchar();
	bool p=0;
	for(;c<'0'||c>'9';c=getchar())
		p=(c=='-'||p)?1:0;
	for(;c>='0'&&c<='9';c=getchar())
		x=x*10+(c-'0');
	return p?-x:x;
}
bool judge(ll x)//判断是否是质数
{
	int i;
	if(!x||x==1)//特判0和1
		return false;
	for(i=2;1LL*i*i<=x;i++)//朴素根号n试除法判断
		if(!(x%i))
			return false;
	return true;
}
int main()
{
	int i,n,m,t,s;
	ll x,y;
	t=re();
	while(t--)//多组数据
	{
		x=y=s=0;//初始化为0
		n=re();
		m=re();
		for(i=1;i<=n+m;i++)//因为异或的性质，我们可以一次性读完并异或
		{
			y=re();
			if(y!=1)//注意！因为无论有多少个1，都是不影响结果的，所以在异或时要把1排除
			{
				i>n?s--:s++;//显然（除去1后）只有当a里的数比b里的数多一个时才可能是质数，所以我们通过统计来判断
				x^=y;//将所有数异或起来，如果满足上述“多一个”的条件，则异或完所剩下的必是没有被约分的数
			}
		}
		if(s==1&&judge(x))//判断是否满足上述“多一个”的条件，且这个剩余的数是否质数
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

另外，我用下面这个数据，将一个题解卡掉了

1
5 2
1 1 1 2 3
1 2

正确输出：YES