值域范围内和倍数有关的一种分组方法+分组问题处理出上下界+通过调和级数按顺序枚举因倍数：ARC141D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133248890

2m2m 个数分成 mm 组，一种合法方案必然是 m+1∼2Mm+1\sim 2M

所以考虑对每个数进行分组

Trick1 值域范围内和倍数有关的一种分组方法

思考方法：每个数 x=k2ix=k2^i ，放在第 kk 组里

直观理解：每个奇数不断翻倍在一个组内

通过这样子，就可以正好可以分成 mm 组

为什么这样分？

  1. 存在一种方法每一组拿一个数

  2. 每组内最多拿一个

所以已经转化为每组 恰好 选一个的问题了

Trick 2 分组问题处理出上下界+通过调和级数按顺序枚举因倍数

对于每一组，我们可以求出其上下界

上界我们希望越大越好，下界我们希望越小越好

枚举上界时，我们要满足其因数不被选。所以对应之前的组，选越大越好，正好对应上界。

下界同理。满足其倍数不被选，所以比它大的越小越好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 600010
//#define M
//#define mo
int n, m, i, j, k, T;
int UP[N], DW[N], c[N], a[N]; 
vector<int>v[N]; 

void all_no() {
	for(i=1; i<=n; ++i) printf("No\n"); 
}

int check(int x) {
	for(int y=x; y<=2*m; y+=x) if(c[y]) return 0; 
	return 1; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) {
		a[i]=k=read(); 
		while(k%2==0) k/=2; v[k].pb(a[i]); 
//		printf("%lld -> %lld\n", a[i], k); 
		
	}
	for(i=1; i<=2*m; i+=2) {
		if(!v[i].size()) return all_no(), 0; 
		for(j=v[i].size()-1; j>=0 && c[v[i][j]]; --j); 
		if(j==-1) return all_no(), 0; 
		UP[i]=j; 
		for(k=v[i][j]*2; k<=2*m; k+=v[i][j]) c[k]++; 
//		printf("UP[%lld]=%lld\n", i, UP[i]) ; 
	}
	for(i=1; i<=2*m; ++i) c[i]=0; 
	for(i=2*m-1; i>=1; i-=2) {
		if(!v[i].size()) return all_no(), 0; 
		for(j=0; j<v[i].size(); ++j) if(check(v[i][j])) break; 
		if(j==v[i].size()) return all_no(), 0; 
		DW[i]=j; c[v[i][j]]=1; 
	}
//	for(i=1; i<=2*m; i+=2) printf("%lld %lld\n", v[i][DW[i]], v[i][UP[i]]); 
	for(i=1; i<=2*m; i+=2) if(DW[i]>UP[i]) return all_no(), 0; 
	for(i=1; i<=n; ++i) {
		k=a[i]; 
		while(k%2==0) k/=2; 
		if(a[i]>=v[k][DW[k]] && a[i]<=v[k][UP[k]]) printf("Yes\n"); 
		else printf("No\n"); 
	}
	return 0;
}