给定一个数字 A，这个 A 由 a1,a2,⋯,aN相乘得到。 给定一个数字 B，这个 B 由 b1,b2,⋯,bM相乘得到。
如果 A/B 是一个质数，请输出YES，否则输出NO。
每个测试点包含多组数据，第一行读入一个整数 TTT 表示数据组数，对于每组数据：
第一行输入两个整数 N,M ，分别表示 A 由 N 个数字相乘得到， B 由 M 个数字相乘得到。
第二行输入 N 个整数，分别表示组成 A 的 N 个数字。
第三行输入 M 个整数，分别表示组成 B 的 M 个数字。
保证对于一个数字，其在 bi 中出现的次数不多于在 ai 中出现的次数。
对于每组数据：
如果 A/B 是一个质数，请输出YES，否则输出NO。
在输出YES或NO后输出一个换行符。
2 3 2 5 7 7 5 7 4 2 5 7 7 7 5 7
YES NO
1≤M≤N≤1000001
1≤ai,bi≤10121
1≤T≤10
∑N≤100000
划重点：
保证对于一个数字，其在 bi 中出现的次数不多于在 ai 中出现的次数。
也就是说 在把相同的构成数约掉之后，分母会约到一
于是此题约掉相同因子后转化为
给 n - m 个正整数 ai ( 1 < = i < = n - m , 1 < = ai < = 1 e 12 ) 求这些数乘起来是否为质数
然后xjb乱搞不是随随便便！！！(完结撒花
设k=n-m，遍历a数组，如果一个数既满足是约剩下的，又值为1的话，k–（表示有用的数又少了一个！(撒花）
最后如果k==1，表示恰好剩下了一个有用的数，那么判断这个有用的数是否为质数 是输出yes否输出no
否则 如果k==0 也就是说分子和分母一样 也就是说A/B==1 且1不是质数 所以输出no
而k>=2时，显然分子由k个非零且非一的数乘起来，那还质数个毛线啊质，输出no
/考场代码 思路不清晰 凑合看
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; #define R register long long a[100007]; long long b[100007]; /* inline long long read() { char ch=getchar(); long long x=0;bool s=1; while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return s?x:-x; } */ int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(R int i=1;i<=n;++i) scanf("%lld",&a[i]); sort(a+1,a+n+1); for(R int i=1;i<=m;++i) scanf("%lld",&b[i]); sort(b+1,b+m+1); if(n-m==0){cout<<"NO"<<endl;} else { int i=1,j=1; while(a[i]==1)++i; while(b[j]==1)++j; int k=n-m-i+j; if(k!=1){cout<<"NO"<<endl;} //else if(k==0){cout<<"YES"<<endl;} else { while(a[i]==b[j])++i,++j; long long x=a[i],flag=0; //cout<<x<<endl; for(long long i=2;i<=sqrt(x)&&!flag;++i) if(x%i==0)flag++; if(!flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } } return 0; }转载于:https://www.cnblogs.com/qwerta/p/9379753.html
