来点gcd (思维 数论

添加链接描述
题意给定一个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;
}
上一篇:拓展欧几里得


下一篇:君君算法课堂-数论基础