包含
GCD
https://ac.nowcoder.com/acm/contest/7607/A
通过化简易知道,题目要求是否中的一个元素,使得为的子集
每次读入时,将的每个子集暴力加入桶中,之后地判断
显然,这样的时间复杂度为
所以我们在的时候进行剪枝,因为当桶中存在值时的子集也存在桶中,此时可以
时间复杂度为
#include<bits/stdc++.h> using namespace std; # define Type template<typename T> # define ll long long # define read read1<ll>() Type T read1(){ T t=0;char k; bool v=0; do (k=getchar())=='-'&&(v=1);while('0'>k||k>'9'); while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar(); return v?-t:t; } bool vis[1000005]; int s,m; void dfs(int x){ if(vis[x]||!x)return; vis[x]=1; for(int i=0;i<20;++i) if(x>>i&1) dfs(x^(1<<i)); } int main(){ s=read;m=read; for(int i=1;i<=s;++i) dfs(read); vis[0]=1; for(int i=1;i<=m;++i) puts(vis[read]?"yes":"no"); return 0; }