Description：

给出 $n$ 个数，问最少选几个数，使他们的 $gcd=1$ 。

$1\leqslant n,a_i\leqslant 300000$

Solution：

首先如果答案存在，那答案一定不大于 $7$ ，因为前 $7$ 个质数之和大于 $3\times 10^5$ ，于是我们可以设计这样一个 $DP$ ： $f[i][j]$ 表示选了 $i$ 个数， $\gcd=j$ 的方案数，那么最后就变成了判断方案数是否 $\ne 0$ ，于是预处理一个 $cnt[i]$ 表示有几个数是 $i$ 的倍数，然后就可以反演/容斥了： $$ f[i][j]=\binom{cnt[j]}{i}-\sum_{k=2}f[i][j\times k] $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 300010

#define MAX 300000

int a[MAXN];

int f[8][MAXN];

#define MOD 998244353

int fac[MAXN],inv[MAXN],ifac[MAXN];

int cnt[MAXN],cntt[MAXN];

int C(int n,int m)

{

	if(n < m)return 0;

	return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]),++cntt[a[i]];

	fac[0] = 1;inv[1] = 1;ifac[0] = 1;

	for(int i = 1;i <= MAX;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	for(int i = 2;i <= MAX;++i)inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;

	for(int i = 1;i <= MAX;++i)ifac[i] = 1ll * ifac[i - 1] * inv[i] % MOD;

	for(int i = 1;i <= MAX;++i)

		for(int k = 1;k * i <= MAX;++k)cnt[i] += cntt[k * i];

	for(int i = 1;i <= 7;++i)

	{

		for(int j = MAX;j >= 1;--j)

		{

			f[i][j] = C(cnt[j],i);

			for(int k = 2;j * k <= MAX;++k)

			{

				f[i][j] = (f[i][j] - f[i][j * k] + MOD) % MOD;

			}

		}

		if(f[i][1] != 0)

		{

			cout << i << endl;

			return 0;

		}

	}

	cout << -1 << endl;

	return 0;

}