P8792

COsm0s · 2023-02-25 20:15:18 · 题解

题意

每次操作选择数组中任意两个相邻的元素 x, y 并将其中的一个元素替换为 \gcd(x, y)。请问最少需要多少次操作才能让整个数组只含 1。

思路

让整个数组变成 1，也就意味着只要有一个数为 1 就行了（性质显然）。

那么此时问题就转化成用最少的操作数使数组中至少有一个数变成 1。

再看题目，发现操作的两数必须是相邻两数进行，也就意味着这个 1 必须由一个区间内推出。换句话说要找到一个区间，使得此区间最大公因数为 1。

那问题就简单了，我们用线段树或 ST 表维护区间 gcd，再枚举区间（运用双指针，two-pointer），就可以求出答案了。

复杂度 O(n\log n\log a_i)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
inline int read() {
    int x = 0, m = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') m = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * m;
}
inline void write(int x) {
    if(x < 0) putchar('-'), write(-x);
    else {
        if(x >= 10) write(x / 10);
        putchar(x % 10 + 48);
    }
}
int n, a[N];
int Gcd[N], cnt;
inline void Build(int x, int l, int r) {
    if(l == r) {
        Gcd[x] = a[l];
        return ;
    }
    int mid = l + r >> 1;
    Build(x << 1, l, mid);
    Build(x << 1 | 1, mid + 1, r);
    Gcd[x] = __gcd(Gcd[x << 1], Gcd[x << 1 | 1]);
}
inline int Query(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) {
        return Gcd[x];
    }
    int ans = 0;
    int mid = l + r >> 1;
    if(L <= mid) ans = __gcd(ans, Query(x << 1, l, mid, L, R));
    if(R > mid) ans = __gcd(ans, Query(x << 1 | 1, mid + 1, r, L, R));
    return ans;
}
//线段树维护区间 gcd
signed main() {
    n = read();
    for(int i = 1; i <= n; i ++) a[i] = read(), cnt += (a[i] == 1);
    Build(1, 1, n);
   if (cnt) return cout << n - cnt, 0;
    int ans = 1 << 30, j = 1;
    for(int i = 1; i <= n; i ++) {
        while(j < i && Query(1, 1, n, j + 1, i) == 1) ++ j;
        if(Query(1, 1, n, j, i) == 1) ans = min(ans, i - j);
    }
    //双指针求出最小区间长度
    if(ans == (1 << 30)) write(-1);
    else write(n + ans - 1);
    return 0;
}