题解 CF1043F 【Make It One】

· · 题解

提供一种简单直接暴力的推式子办法。

首先发现答案必定 \leqslant 7。否则必定无解。

我们考虑记录取 t 个数的时候，每个数作为 \gcd 出现的方案数。

有

c_k = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j)=k]a_ib_j

这玩意是个 \gcd 卷积状物。对于这种玩意我们是有 O(n\ln n) 的做法的。具体地，我们考虑先求出 d 数组表示不考虑 \gcd 条件的方案数，即为反演的 F 函数。可以简单地枚举倍数。然后反演。枚举倍数即可。

const int MAXN = 3e5 + 5;
#define vi vector < int > 
vi a, st; int n, m, val[MAXN];
int mu[MAXN], prime[MAXN], tot, vis[MAXN];
void init(int n = MAXN - 5) {
    mu[1] = 1;
    For(i, 2, n) {
        if(!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * prime[j] <= n; j++) {
            int to = i * prime[j]; vis[to] = 1;
            if(i % prime[j] == 0) {
                mu[to] = 0; break;
            } else mu[to] = -mu[i];
        }
    }
}
vi operator * (const vi &a, const vi &b) {
    vi ans(m + 5);
    For(i, 1, m) {
        int t1 = 0, t2 = 0;
        for(int j = 1; i * j <= m; j++)
            t1 += a[i * j], t2 += b[i * j];
        ans[i] = t1 * t2;
    }
    For(i, 1, m)
        for(int j = 2; i * j <= m; j++)
            ans[i] += ans[i * j] * mu[j];
    return ans;
}
signed main()
{
    #ifndef ONLINE_JUDGE
        file("pro");
    #endif
    n = read(); 
    For(i, 1, n)
        val[i] = read(), ckmax(m, val[i]);
    init(); st.resize(m + 5); 
    For(i, 1, n) st[val[i]] = 1;
    if(st[1]) return printf("1\n"), 0;
    a = st;
    For(i, 1, 6) {
        a = a * st;
        if(a[1]) return printf("%lld\n", i + 1), 0;
    }
    printf("-1\n");
    return FastIO::Fflush(), 0;
}