当前位置: 代码迷 >> 综合 >> 洛谷 P4752 Divided Prime
  详细解决方案

洛谷 P4752 Divided Prime

热度:98   发布时间:2023-12-01 21:38:25.0

题目其实很简单,主要坑点是 数组中的 1
代码:

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=200000+100;int prime[maxn],tot;
bool isprime[maxn];ll a[maxn],b[maxn];void init(){for(int i=0;i<maxn;i++) isprime[i]=true;isprime[0]=isprime[1]=false;tot=0;for(int i=2;i<maxn;i++){if(isprime[i]) prime[tot++]=i;for(int j=0;j<tot && i*prime[j]<maxn;j++){isprime[i*prime[j]]=false;if(!(i%prime[j])) break;}}
}int main(){init();int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);int onea=0;int oneb=0;for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);if(a[i]==1) onea++;}for(int i=1;i<=m;i++) {scanf("%lld",&b[i]);if(b[i]==1) oneb++;}if(n-m>=2+onea-oneb || n==m) printf("NO\n"); //多于两个及以上不为1的数就肯定不是素数了else{ll num=0;for(int i=1;i<=n;i++) if(a[i]!=1) num^=a[i];for(int i=1;i<=m;i++) if(b[i]!=1) num^=b[i];bool isok=true;for(int i=0;i<tot && isok;i++){if((ll)prime[i]*prime[i]>num) break;if(num%prime[i]==0) isok=false;}if(num && isok) printf("YES\n"); //num!=0else printf("NO\n");}}
}