点此看题
首先给出结论，任意取出 [ 2 , n − 1 ] [2,n-1] [2,n−1]个数的 gcd \gcd gcd的并集就是最后的答案。
我们尝试构造这种方法，首先先取三个数出来，拿我们想要的那两个数的 gcd \gcd gcd，然后拿这两个重复的 gcd \gcd gcd和其他数操作，如果 gcd \gcd gcd想要合并其他的数那么就选当前的 gcd \gcd gcd和其他的数，如果不想合并那么选两次这个 gcd \gcd gcd即可。实现就使用搜索，搜索没有出现过的值。
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int M = 1005; #define pii pair<int,int> int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int T,n,a[M],ok[M];queue<pii> q; int gcd(int a,int b) { return !b?a:gcd(b,a%b); } signed main() { scanf("%d",&T); while(T--) { scanf("%d",&n); memset(ok,0,sizeof ok); while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int t=gcd(a[i],a[j]); if(!ok[t]) ok[t]=1,q.push(make_pair(t,2)); } while(!q.empty()) { pii t=q.front();q.pop(); if(t.second==n-1) break; for(int i=1;i<=n;i++) { int tmp=gcd(t.first,a[i]); if(!ok[tmp]) ok[tmp]=1,q.push(make_pair(tmp,t.second+1)); } } int flag=0; for(int i=1;i<=1000;i++) if(ok[i]) { if(flag) printf(" %d",i); else printf("%d",i),flag=1; } puts(""); } }