题目描述
给定一个数字 AA ，这个 AA 由 a_1,a_2,cdots,a_Na1,a2,⋯,aN 相乘得到。
给定一个数字 BB ，这个 BB 由 b_1,b_2,cdots,b_Mb1,b2,⋯,bM 相乘得到。
如果 frac{A}{B}BA 是一个质数，请输出YES，否则输出NO。
输入输出格式
输入格式：
每个测试点包含多组数据，第一行读入一个整数 TT 表示数据组数，对于每组数据：
第一行输入两个整数 N,MN,M ，分别表示 AA 由 NN 个数字相乘得到， BB 由 MM 个数字相乘得到。
第二行输入 NN 个整数，分别表示组成 AA 的 NN 个数字。
第三行输入 MM 个整数，分别表示组成 BB 的 MM 个数字。
保证对于一个数字，其在 {b_i}bi 中出现的次数不多于在 {a_i}ai 中出现的次数。
输出格式：
对于每组数据：
如果 frac{A}{B}BA 是一个质数，请输出
YES，否则输出NO。在输出
YES或NO后输出一个换行符。
输入输出样例
说明
1 le N le 1000001≤N≤100000
0 le M le N0≤M≤N
1 le a_i,b_i le 10^{12}1≤ai,bi≤1012
1 le T le 101≤T≤10
sum N le 100000∑N≤100000
Solution:
看清题目中给出的性质，本题就比较傻逼了。
题中说到保证$b$中出现的数的次数不超过$a$中该数出现的次数，于是不难想到统计$a$中各数出现的次数（注意是非$1$的数），然后在$b$中将这些数出现的次数从$a$中抵消，若$a$中非$1$的数出现次数大于$b$中出现的次数$+1$或者$a$中非$1$数的次数等于$b$中非$1$数出现次数，则直接输出$NO$（前者因为两个数相乘一定是合数，后者因为直接抵消约分得非质数$1$），然后取出模拟约分过程后的剩下的一个数，直接$O(sqrt n)$判断是否是质数就好了，而前面约分的情况直接用$multiset$就好了，整体时间复杂度$O(t*(nlog n+sqrt n))$。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) using namespace std; const int N=100005; ll T,n,m; multiset<ll>s; il ll gi(){ ll a=0;char x=getchar(); while(x<'0'||x>'9')x=getchar(); while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar(); return a; } int main(){ T=gi(); while(T--){ n=gi(),m=gi(); int la=0,lb=0;ll x; s.clear(); For(i,1,n) {x=gi();if(x!=1)la++,s.insert(x);} For(i,1,m) {x=gi();if(x!=1){lb++,s.erase(s.find(x));}} if(la>lb+1||la==lb){puts("NO");continue;} x=*s.begin(); bool f=0; for(ll i=2;i*i<=x;i++) if(x%i==0) {puts("NO");f=1;break;} if(!f)puts("YES"); } return 0; }