题目描述
给你一个长度为 \(n\) 的序列 \(A_i\) ，问你最少能从这个集合中取出多少数使得其 \(\gcd=1\)
数据范围
\(1\leq n\leq 3\times 10^5\)；\(1\leq a_i \leq 3\times 10^5\).
思路：
首先观察一下这个数据范围，其中小于 \(3\times 10^5\) 的质因数个数为 \(6\)。
所以我们可以考虑一种最大化的构造方式：
x1=2*3*5*7*11*13
x2=2*3*5*7*11 * 17
x3=2*3*5*7 * 13*17
x4=2*3*5 * 11*13*17
x5=2*3 * 7*11*13*17
x6=2 * 5*7*11*13*17
x7= 3*5*7*11*13*17
所以上界应该是 \(7\)
所以我们不妨去枚举这个上界，然后想办法进行计算。
首先令 \(cnt_i\) 表示在数列中为 \(i\) 的倍数的个数
\(f_i\) 表示 \(\gcd=i\) 的方案数
\(g_i\) 表示 \(\gcd=ki\) 的方案数
所以可以非常轻松的列出转移方程：
\(g_i=\binom{cnt_i}{k}\)
\(f_i=g_i-\sum\limits_{i|j}^{j\leq lim}f_j\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb push_back
#define pt putchar
#define T int t;cin>>t;while(t--)
#define begin init()
#define rand RAND
#define LOCAL
#define pii pair<int,int>
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=3e5+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int fac[maxn],inv[maxn];
int qp(int x,int k){int res=1;while(k){if(k&1)res=res*x%mod;x=x*x%mod;k>>=1;}return res;}
void init(){int mx=maxn-5;fac[0]=1;for(int i=1;i<=mx+1;i++)fac[i]=fac[i-1]*i%mod;inv[mx+1]=qp(fac[mx+1],mod-2);for(int i=mx;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;}
int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);return;}
int n,m;
int a[maxn];
int mn,mx[maxn];
int f[maxn],g[maxn];
signed main(){
begin;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],mx[a[i]]++;
int lim=*max_element(a+1,a+n+1);
for(int i=1;i<=300000;i++){
for(int j=i+i;j<=300000;j+=i)
mx[i]+=mx[j];
}
for(int k=1;k<=7;k++){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=1;i<=lim;i++)g[i]=C(mx[i],k);
for(int i=lim;i>=1;i--){
f[i]=g[i];
for(int j=i+i;j<=lim;j+=i)f[i]=(f[i]-f[j]+mod)%mod;
}
if(!mn&&f[1])mn=k;
}
if(!mn)puts("-1");
else cout<<mn<<endl;
return 0;
}