首先观察易得答案不会超过 \(7\)。
证明：可以构造极限情况：
\[2*3*5*7*11 , 2*3*5*7*13,...
\]
所以可以枚举答案，看是否满足。
是否满足的题我们通常可以计算方案数来判断。
于是考虑动态规划，定义状态 \(f_i\) 表示选了 \(s(1\leq s \leq 7)\) 个数，此时 \(\gcd\) 为 \(i\) 的方案数。
同时定义 \(g_i\) 表示元素大小为 \(i\) 的倍数的数的个数，\(V\) 表示值域。
考虑转移： $$f_i = \binom{g_i}{s} - \sum_{j=2}^{\frac{V}{i}}f_{ij}$$
最后结果判断 \(f_1\) 是否为 \(0\) 即可。
时间复杂度 \(\mathcal{O(n \ln n)}\).
#include<bits/stdc++.h>
#define ll long longusing namespace std;const ll N = 3e5+5,V = 3e5,mod = 1e9+7;int n;
ll a[N];
ll g[N],f[N],fac[N],inv[N];ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}ll C(int a,int b){return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main() {cin>>n;for(int i=1;i<=n;i++)cin>>a[i],g[a[i]]++;fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=qpow(n,mod-2);for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;for(int i=1;i<=V;i++){for(int j=2;j<=V/i;j++)g[i]+=g[i*j];}for(int s=1;s<=7;s++){for(int i=1;i<=V;i++)f[i]=0;for(int i=V;i>=1;i--){ll res=0;if(g[i]<s)continue;for(int j=2;j<=V/i;j++)res=(res+f[i*j])%mod;f[i]=(C(g[i],s)-res+mod)%mod;}if(f[1]>0){cout<<s;return 0;}}cout<<-1;return 0;
}