[蓝桥杯 2022 国 B] 齿轮(优化枚举）

        根据题目描述，如果采用dfs暴力做法枚举所有方案，肯定会超时，因此我们需要优化枚举，我们都知道在同一组共同转动的齿轮中，线速度相等，因此角速度的比值就是半径的反比，因此我们只需要找到对于每个齿轮作为起始齿轮，只需要找到其倍数半径是否存在即可，而倍数上限就是假设存在半径为1的齿轮，其中最大半径的齿轮就是转速上限，再用bool类型的ans数组记录该倍数是否存在即可，需要注意的是可以用set数组去重，如果存在重复的齿轮，就可以证明ans[1]肯定蹲在，最后只需要进行访问即可

上代码

#include<iostream>
#include<cstring>
#include<unordered_set>
#include<algorithm>

using namespace std;
const int N = 2e5 + 10;
bool ans[N];

int main(void)
{
	int n, q; cin >> n >> q;
	unordered_set <int> st;//统计齿轮，并且去重 
	int mx = 0;
	for(int i = 1; i <= n; i++){
		int r; cin >> r;
		if(st.count(r)) ans[1] = true;//如果存在重复，说明1倍转速可以存在 
		st.insert(r);
		mx = max(mx, r);//假设存在半径为1的齿轮，那么最大倍数就是mx 
	}
	
	for(auto i = st.begin(); i != st.end(); i++){
		for(int j = (*i) * 2; j <= mx; j+=(*i)){//j从二倍半径开始枚举，枚举到上限mx
			if(st.count(j)) ans[j / (*i)] = true;//如果存在半径j，就记录答案 
		}
	}
	
	while(q--){
		int x; cin >> x;
		if(ans[x]) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;	
}