·首先，理解一下题意，给定一个序列，对每个查询，输出该序列是否存在子序列的gcd（最大公约数）为查询所给的数。

·我们知道，对最开始的序列中的重复的数，其对gcd其实没有影响（对与其相等的数，gcd就是它自己，对与其不等的数，gcd也都是一样的）；

·所以我们可以先把序列去重（以题上的{2, 2, 6, 6, 2, 1, 5}）为例

{2, 2, 6, 6, 2, 1, 5} --> {2, 6, 1, 5}

·最终把序列里的所有数存在vis里

		for (int i = 0; i < n; i ++ )
		{
			int num;
			scanf("%d", &num);
			vis[num] = 1;
		}

·然后对于查询给出的数

·显然可能以其为gcd的数只有可能为它的倍数

·以只可能为倍数倍数这点，我们想到经典的“调和级数”遍历方式

·然后对原序列中的所有查询的数的倍数取gcd, 若gcd与查询的数相等，则说明存在子序列的gcd等于查询的数。（因为都是倍数，gcd最小只会到查询的数，我们知道一个序列的gcd是单调不增的，所以最后的gcd与查询的数相等必然有子序列的gcd为查询的数）

·所以可以预处理一遍1~n的所有数看是否满足条件存到res里

·最后查询的时候看每个数是否在res里即可

		for (int i = 1; i <= n; i ++ )
		{
			int num_gcd = 0;
			for (int j = i; j <= n; j += i)
			{
				if (vis[j]) num_gcd = gcd(j, num_gcd);
			}
			if (num_gcd == i) res[i] = 1;
		}

·完整代码 复杂度O(nlogn + m)

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m;

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T -- )
	{
		scanf("%d%d", &n, &m);
		vector<int> vis(n + 10, 0);
		vector<int> res(n + 10, 0);
		for (int i = 0; i < n; i ++ )
		{
			int num;
			scanf("%d", &num);
			vis[num] = 1;
		}
		for (int i = 1; i <= n; i ++ )
		{
			int num_gcd = 0;
			for (int j = i; j <= n; j += i)
			{
				if (vis[j]) num_gcd = gcd(j, num_gcd);
			}
			if (num_gcd == i) res[i] = 1;
		}
		
		for (int i = 0; i < m; i ++ )
		{
			int num;
			scanf("%d", &num);
			if (res[num]) puts("YES");
			else puts("NO");
		}
	}
	
	return 0;
 }

·这里顺便解释一下为什么调和级数遍历的复杂度是O(nlogn)

·首先对

		for (int i = 1; i <= n; i ++ )
		{
			for (int j = i; j <= n; j += i)
			{
				***
			}
		}

·显然这样遍历的复杂度为

·把n提出来得到

(后面乘的就是调和级数)

·所以有

·所以复杂度为O(nlogn)

(但是证明过程中有个小于号，所以其实会比O(nlogn) 还快不少)

·希望对大家有所帮助qwq