添加链接描述
题意给定一个x问是否可以找到一个子集使得其中有大于等于k的个数的gcd等于x
大于等于其实是个烟雾弹,可以找到更短的就不需要找到更长的了,所以满足等于k即可。
找到集合的gcd要等于k也就是说集合的每个数都是k的倍数,通过数组桶存贮来表示当前这个数是否在数组中存在。添加链接描述
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int arr[N],res[N];
int gcd(int x, int y) {
return y? gcd(y, x % y) : x;
}
void solve(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++){
arr[i]=0,res[i]=0;
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
arr[x]++;
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
if(arr[j]){
res[i]=gcd(res[i],j);
}
}
}
while(m--){
int x;
scanf("%d",&x);
if(res[x]==x)puts("YES");
else puts("NO");
}
}
int main(){
int T;
// cout<<__gcd(0,2)<<endl;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}