CF1043F Make It One 及变式

Description

给定 $n$ 个数 $a_i$ ，请找出一个子集，满足子集的 $\gcd=1$ ，并且子集元素个数尽可能少。
$1\leq n,a_i\leq 3\times 10^5$

Solution

如果 $a$ 是 $b$ 的因子，那么我们肯定不会选 $b$ 。也就是说每个数的质因子次数不超过 $1$ 。
由于 $3\times 10^5$ 至多被拆成 $6$ 个不同质数之积，所以答案不会超过 $7$ 。

既然答案范围很小，那么我们直接最优化转可行性判定。
枚举 $k$ ，判断在选择 $k$ 个数的情况下是否存在集合最小公因数为 $1$ 。

设 $\text{cnt}_i$ 表示 $\sum\limits_{j=1}^{n}[a_j=i]$。
令

$F(x)=\sum\limits_{i=1}^{n}\text{cnt}_{i}x^{i}$

那么我们要求的就是 $[x]F^{i}$，其中乘法定义为 $\gcd$ 卷积。
$\gcd$ 卷积本质上就是高维 $\min$ 卷积，那么做 $\gcd$ 卷积的办法为高维后缀和/后缀差分。求高维后缀和的方法有两种，一种方法是用 $\mu$ 来容斥，一种方法是一维一维累加，前者复杂度 $\mathcal{O}(V\ln V)$ ，后者 $\mathcal{O}(V\log\log V)$ 。

博主采取的是第二种办法。

Code

const int N = 3e5 + 233, mod = 1e9 + 9;
using namespace std;
int n, m, num;
int a[N], F[N], G[N], tmp[N];
int pr[N], ok[N];
void Sieve(int n){
    for(int i = 2; i <= n; ++i){
        if(!ok[i]) pr[++num] = i;
        for(int j = 1; j <= num and pr[j] * i <= n; ++j){
            ok[i * pr[j]] = 1;
            if(i % pr[j] == 0) break;
        }
    }
}
inline void Plus(int &a, int b){
    a += b - mod, a += (a >> 31) & mod;
}
void presum(int *f){
    for(int i = 1; i <= num; ++i){
        int p = pr[i];
        for(int j = m / p; j >= 1; --j)
            Plus(f[j], f[j * p]);
    }
}
void divsum(int *f){
    for(int i = 1; i <= num; ++i){
        int p = pr[i];
        for(int j = 1; j <= m / p; ++j)
            Plus(f[j], mod - f[j * p]);
    }
}
int GCD(int a, int b){
    return !b ? a : GCD(b, a % b);
}
int main(){

    fin >> n;
    int gcd = 0;
    for(int i = 1, x; i <= n; ++i)
        fin >> x, gcd = GCD(x, gcd), ++F[x], m = max(m, x);
    if(gcd > 1){
        puts("-1");
        return 0;
    }

    Sieve(m);

    presum(F);
    for(int i = 1; i <= m; ++i)
        G[i] = F[i];

    int sum = 1;
    while(true){
        for(int i = 1; i <= m; ++i)
            tmp[i] = F[i];
        divsum(tmp);
        if(tmp[1])
            cout << sum << endl, exit(0);
        for(int i = 1; i <= m; ++i)
            F[i] = 1ll * F[i] * G[i] % mod;
        ++sum;
    }
    return 0;
}

More

上述方法并不能求出具体方案。我们考虑这样一个问题：

给定 $n$ 个数，要从中选出 $k$ 个点，满足这 $k$ 个数的最大公因数为 $1$，输出这 $k$ 个数。

目前只有一个 $\mathcal{O}(kn\sqrt{V})$ 的做法。