来点gcd

NC229589. 来点gcd

描述

给定一个有 $n$ 个元素的多重集 $S$ ，有 $m$ 个询问，对于每个询问，给出一个整数 $x$ ，问是否能选择 $S$ 的一个非空子集，满足这个子集的 $gcd$ 等于 $x$ ，当集合只有一个数时，设这个集合的 $gcd$ 就等于这个数， $gcd(x,y)$ 的值为 $x,y$ 的最大公约数

输入描述

多组数据，先读入一个 T 代表组数
对于每组数据 ：
第一行两个正整数 n , m 分别代表集合包含的元素个数和询问个数
第二行 n 个正整数 ai ，代表集合内的具体元素 ( 1 ≤ ai ≤ n )
接下来 m 行每行一个正整数 x 代表当前询问的数 ( 1 ≤ x ≤ n )
保证 T 组数据中 n，m 的总和不超过 1e6

输出描述

输出 m 行，每行输出 “YES”  或者  “NO” ( 不包含引号 )

示例1

输入:

2
7 3
2 2 6 6 2 1 5
3
2
6
7 3
6 3 1 4 6 4 3
7
5
2

输出:

NO
YES
YES
NO
NO
YES

说明:

第一组样例
第一个询问找不到这样的子集
第二个询问取子集 { 2 }
第三个询问取子集 { 6 }
第二组样例
第一个询问找不到这样的子集
第二个询问找不到这样的子集
第三个询问取子集 { 4，6 }

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 874ms, 内存消耗: 50092K, 提交时间: 2021-11-12 17:49:14

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,m,x;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		unordered_map<int,int> h;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			h[x]++;
		}
		while(m--){
			scanf("%d",&x);
			int p=0;
			for(int i=x;i<=n&&p!=x;i+=x){
				if(h[i]) p=__gcd(i,p);
			}
			if(p==x) puts("YES");
			else puts("NO"); 
		}
	}
	return 0;
}

上一题

下一题

详情