【齿轮——优化（预处理，去重，哈希）】

题目

分析

在线暴力枚举： //询问，枚举齿轮，枚举另一齿轮

采用哈希优化：不用再枚举另一齿轮 

预处理，但仍是暴力枚举，枚举q： //q范围，枚举齿轮；枚举齿轮//枚举齿轮，枚举倍数

采用去重优化：枚举齿轮和枚举倍数的复杂度之积稳定在

因此采用的优化是：预处理+哈希+去重

此外要注意n=1的情况，ans[1]=1；以及哈希的时候要排除自身，不然询问1就G了

代码 #include <bits/stdc++.h> using namespace std; const int N = 2e5+10; int a[N], h[N], ans[N]; int n, m; int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", a+i), h[a[i]]++; sort(a+1, a+n+1); n = unique(a+1, a+n+1) - a - 1; if(n == 1) ans[1] = 1; //自身:自身=1 for(int i = 1; i <= n; i++) { h[a[i]]--; //除去自身 for(int j = a[i]; j < N; j += a[i]) if(h[j]) ans[j / a[i]] = 1; h[a[i]]++; //回溯 } while(m--) { int x; scanf("%d", &x); if(ans[x]) puts("YES"); else puts("NO"); } }