ARC141D

关键点在于 \(M\le N\le2M\) 的条件。

结论：在 \(1\sim2M\) 中至多选出 \(M\) 个数使得它们两两不为整除关系。

证明：鸽巢原理。考虑把每个数写成 \((x,y)\) 表示 \(A_i=x\times 2^y\)，其中 \(x\) 是奇数，然后把这个数的 \(y\) 丢进桶 \(x\) 里，发现每个桶只能选恰好一个，而桶的数量就是 \(M\)。

接下来就很套路了，如果两个桶 \(a=kb\)，那么 \(b\) 桶中选的数一定大于 \(a\) 桶中选的数，那么就可以贪心的求出每个桶中能取得的最大值/最小值。

时间复杂度 \(\mathcal O(N\ln N)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 600005;
int n, m;
int a[N];
int f[N], g[N], w[N];
vector <int> cnt[N];

void ret() { while (n--) printf("No\n"); exit(0); }
void chkmax(int &a, int b) { if (a < b) a = b; }
void chkmin(int &a, int b) { if (a > b) a = b; }

int main() {
	scanf("%d%d", &n, &m), m <<= 1;
	for (int i = 1, x; i <= n; ++i) {
		scanf("%d", &x), a[i] = x;
		int y = __builtin_ctz(x);
		cnt[x >> y].push_back(y);
	}
	for (int i = 1; i <= m; ++i) if ((i & 1) && cnt[i].empty()) ret();
	memset(f, 0xcf, sizeof f), memset(w, 0xcf, sizeof w);
	for (int i = m; i; --i) if (i & 1) {
		for (int j = i + i; j <= m; j += i) chkmax(f[i], w[j]);
		if (f[i] >= cnt[i].back()) ret();
		w[i] = *upper_bound(cnt[i].begin(), cnt[i].end(), f[i]);
	}
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= m; ++i) if (i & 1) {
		if (g[i] <= cnt[i].front()) ret();
		w[i] = *--lower_bound(cnt[i].begin(), cnt[i].end(), g[i]);
		for (int j = i + i; j <= m; j += i) chkmin(g[j], w[i]);
	}
	for (int i = 1; i <= n; ++i) {
		int y = __builtin_ctz(a[i]);
		int x = a[i] >> y;
		printf("%s\n", (f[x] < y && y < g[x]) ? "Yes" : "No");
	}
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16818877.html