题解 P4752 【Divided Prime】

**这是一个不需要$STL$的方法** 因为每个因子都很大，所以我们不可能直接乘起来再除~~（这不是废话）~~，而题目保证对于一个数字，其在$b_i$中出现的次数不多于在$a_i$中出现的次数，所以我们很容易想到要把$a$中的数用$b$里的约分掉，而众所周知，$a\land a=0$，于是我们就可以考虑利用**异或**来约分，主要细节看代码说吧。 ```cpp #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; } ``` 另外，我用下面这个数据，将一个题解卡掉了 ```cpp 1 5 2 1 1 1 2 3 1 2 正确输出：YES ```