[CF1043E]Make It One

Link

Solution

将找最小值变成求是否可行,而求是否可行的方法又是容斥计数判断是否为0,这波操作666
f[i][j]表示选i个数字\gcdj的方案数目,答案就是最小的i使得f[i][1]\not=0
f[i][j]=\binom {i}{c[j]}-\sum_{k=2}f[i][j*k]c[j]表示所有数字中整除j的个数。

Code

const int XN=3e5+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;(v>>=1),(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int main() {
    static int f[8][XN],a[XN],fact[XN],ifact[XN],cnt[XN],c[XN];
    int n,m=0;fin>>n;

    fact[0]=1;
    for(int i=1;i<=n;++i)
        fact[i]=Mul(fact[i-1],i);
    ifact[n]=Pow(fact[n],P-2);
    for(int i=n-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    auto C=[](int n,int m) { return n>=m?Mul(fact[n],Mul(ifact[n-m],ifact[m])):0; };

    for(int i=1;i<=n;++i) {
        fin>>a[i];
        f[1][a[i]]=1;
        Enlarge(m,a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
            c[i]+=cnt[i*j];
    for(int i=2;i<=7;++i) {
        for(int j=m;j>=1;--j) {
            f[i][j]=C(c[j],i);//整除j的个数
            for(int k=2;k*j<=m;++k)
                f[i][j]=Minus(f[i][j],f[i][k*j]);
        }
    }
    int Ans=-1;
    for(int i=1;i<=7;++i)
        if(f[i][1]) {
            Ans=i;
            break;
        }
    fout<<Ans<<'\n';
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注