2 - H

litachloveyou · 2023-08-12 15:56:57 · 个人记录

容易想到，如果原数组有 1 那么只需要输出 n-cnt (cnt 为 1 的个数 )。

若没有 1 ，想让所有数等于 1 ，那么我们肯定是要找到一个连续的区间（操作相邻）让他们的 \gcd 为 1 。

也就是找到一段区间 [l,r] 满足 \gcd(a_l,a_{l+1},...,a_r) = 1 。

找到这样的区间之后构造 1 的花费为 r-l ，举个例子，容易知道 [2,4,9] 这一区间的 \gcd 为 1 ，那么想构造出 1 来就需要 2 次。也就是 \gcd(2,4)=2 ，\gcd(2,9) = 1，构造出 1 后还需要将前面的元素都变成 1 ，这还需要 r-l 次。

所以题目等价于求 \min((r-l)\times2+n-(r-l+1))[\gcd(l,r)=1] ,(r-l)\times2 为找到区间全变成 1 的花费，n-(r-l+1) 为将剩下的元素变成 1 的花费，从式子不难看出，如果找到的区间越短花费越小。

我们可以枚举每一个 l ,找到每一个 l 最近的 r 。因为 r 越大 \gcd 就越可能为 1 ，也就是满足单调性，所以可以二分查找每个 r 。

区间 \gcd 可以使用 st 表来求。时间复杂度为 O(nlogn) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void solve()
{
    int n;
    cin >> n;
    vector<vector<int>>a(n + 1, vector<int>(24));
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][0];
        if (a[i][0] == 1)cnt++;
    }
    if (cnt)
    {
        cout << n - cnt << "\n";
        return;
    }
    for (int j = 1; j <= 22; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            a[i][j] = gcd(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
        }
    }
    auto query = [&](int l, int r)->int
    {
        int k = log2(r - l + 1);
        return gcd(a[l][k], a[r - (1 << k) + 1][k]);
    };
    ll res = 1e18;
    for (int i = 1; i <= n; i++)
    {
        int l = i, r = n;
        int ans = -1;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (query(i, mid) == 1)
            {
                r = mid - 1;
                ans = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if (ans != -1)
        {
            res = min(res, 1LL * (ans - i) * 2 + n - (ans - i + 1));
        }
    }
    if (res >= 1e17)res = -1;
    cout << res << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)solve();
    return 0;
}