Code:
#include <cstdio> #include <algorithm> #define ll long long #define N 300002 #define mod 998244353 #define setIO(s) freopen(s".in","r",stdin) using namespace std; ll fac[N],inv[N]; int arr[N],cnt[N],f[12][300001]; ll qpow(ll base,ll k) { ll tmp=1; for(;k;base=base*base%mod,k>>=1) tmp=tmp*base%mod; return tmp; } ll C(int n,int m) { if(n<m) return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { int i,j,n,M=0; // setIO("input"); scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%d",&arr[i]), cnt[arr[i]]++, f[1][arr[i]]++; M=max(M,arr[i]); if(arr[i]==1) { printf("1\n"); return 0; } } fac[0]=1; for(i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod; inv[N-1]=qpow(fac[N-1],mod-2); for(i=N-1;i>=1;--i) inv[i-1]=i*inv[i]%mod; for(i=1;i<=M;++i) for(j=i+i;j<=M;j+=i) cnt[i]+=cnt[j]; for(i=2;i<=11;++i) { for(j=M;j>=1;--j) { f[i][j]=C(cnt[j], i); for(int k=j+j;k<=M;k+=j) f[i][j]=(f[i][j]-f[i][k]+mod)%mod; } if(f[i][1]>0) { printf("%d\n",i); return 0; } } printf("-1\n"); return 0; }