【蓝桥杯 2022 国 A】 最大公约数

传送门

Solution

首先考虑数组内已经有 $1$ 的情况。设此时有 $n_1$ 个 $1$，则答案为 $n-n_1$。

再考虑数组内没有 $1$ 的情况。要想让整个数组变成 $1$，首先要先在某一段连续的区间内进行 $\gcd$ 操作，生成第一个 $1$。然后通过 $n-1$ 次 $\gcd$，把数组的其余元素变成 $1$。设生成第一个 $1$ 的连续区间长度为 $len$，本题答案即为

$(len - 1) + (n - 1)$

注意到每次操作只能改变一个元素的值，所以这个答案的正确性是显然的。

问题转化为如何找到能生成第一个 $1$，即区间的 $\gcd$ 为 $1$ 的最短区间。如果用朴素的枚举，复杂度为 $\Theta(n^2)$。这里考虑用二分答案 + 线段树优化。线段树 $O(\log n)$ 查询区间的 $\gcd$。注意到左端点确定时，区间的 $\gcd$ 随右端点的增大而递减。因此枚举区间的左端点，二分答案找出符合要求的最小右端点即可。

复杂度 $\Theta(n\log n)$

code

#include <bits/stdc++.h>
#define N 100010
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
    x = 0; T f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

int n, a[N], ans = 1e9, cnt; 
struct Tree {
    int l, r, val;
} T[N << 2];

void build(int k, int l, int r)
{
    T[k].l = l; T[k].r = r;
    if (l == r) {
        T[k].val = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    T[k].val = __gcd(T[ls].val, T[rs].val);
}

int query(int k, int x, int y)
{
    if (x <= T[k].l && T[k].r <= y)
        return T[k].val;
    int mid = T[k].l + T[k].r >> 1, resl = 0, resr = 0;
    if (x <= mid)  resl = query(ls, x, y);
    if (mid < y) resr = query(rs, x, y);
    return __gcd(resl, resr);
}

int main()
{
    freopen("a.txt", "r", stdin);
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        cnt += (a[i] == 1);
    }
    if (cnt) {
        printf("%d", n - cnt);
        return 0;
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int le = i, ri = n, mid, res = n + 1;
        while (le <= ri) {
            mid = le + ri >> 1;
            if (query(1, i, mid) == 1) {
                res = mid;
                ri = mid - 1;
            } else le = mid + 1;
        }
        if (res != n + 1)
            ans = min(ans, res - i + n - 1);
    }
    if (ans == 1e9) printf("-1");
    else printf("%d", ans);
    return 0;
}