Codeforces Round #519 by Botan Investments F. Make It One

https://codeforces.com/contest/1043/problem/F

题意

给你n个数，求一个最小集合，这个集合里面数的最大公因数等于1

1<=n<=3e5

1<=a[i]<=3e5

思路

• 先考虑什么情况下满足集合中的最大公因数=1？
• 集合中的每个数没有共同的素因子，即所有素因子并没有包含于选出集合的所有数中，存在 结论前7个素因子的乘积为510510 ，所以可以得出选出的集合大小最大为7
• 定义dp[i][j]为，集合大小为i，集合最大公因数=j的方案数
• dp[i][j]= \(\begin{pmatrix} cnt[j] \\ i \\ \end{pmatrix}\) - \(\sum_{k=2}^{\infty}\)dp[i][j*k]

处理

• 逆元打表求组合数
• log(3e5)时间处理出每个数的倍数个数cnt[i]
• 从后往前扫求dp[i][j]

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int P =1e9+7;

const int M =3e5+5;

ll F[M],Finv[M],inv[M],dp[20][M],cnt[M];

int n,x,i,j,k;

void init(){

    F[1]=Finv[1]=inv[1]=Finv[0]=inv[0]=1;

    for(int i=2;i<M;i++)inv[i]=inv[P%i]*(P-P/i)%P;

    for(int i=2;i<M;i++){

        Finv[i]=Finv[i-1]*inv[i]%P;

        F[i]=F[i-1]*i%P;

    }

}

ll C(int n,int m){

    if(m<0||n<m)return 0;

    if(m==0||n==m)return 1;

    return F[n]*Finv[n-m]%P*Finv[m]%P;

}

int main(){

    init();

    scanf("%d",&n);

    for(i=1;i<=n;i++){

        cin>>x;cnt[x]++;

    }

    for(i=1;i<M;i++)

        for(j=i+i;j<M;j+=i)

            cnt[i]+=cnt[j];

    for(i=1;i<=15;i++){

        for(j=M-1;j>=1;j--){

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

            for(k=j+j;k<M;k+=j){

                dp[i][j]=(dp[i][j]-dp[i][k]+P)%P;

            }

        }

        if(dp[i][1]>0){

            cout<<i;return 0;

        }

    }

    cout<<-1;

}