【蓝桥杯 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;
}