http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616

这道题主要是查询一个数是不是原有集合的一个子集的所有数的gcd。

只要枚举一个数的倍数暴力判断就可以了，时间复杂度\(O(alna),a=10^6\)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

bool vis[1000003];

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

int main() {

	int n, x, num, ans = 0, top = 0;

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)

		scanf("%d", &x), vis[x] = true, top = max(top, x);

	for (int i = 1; i <= top; ++i)

		if (!vis[i]) {

			num = -1;

			for (int j = (i << 1); j <= top; j += i)

				if (vis[j]) {

					if (num == -1)

						num = j;

					else

						num = gcd(num, j);

					if (num == i)

						vis[i] = true;

				}

		}

	for (int i = 1; i <= top; ++i)

		if (vis[i])

			++ans;

	printf("%d\n", ans);

	return 0;

}