解法：思维
首先处理一些特殊情况：
- 如果整个序列的最大公约数都不是 $1$，那么无解。
- 如果序列里已经存在一些 $1$ 了，那么每次可以选择 $1$ 与它旁边的一个数 $x > 1$，把 $x$ 也变成 $1$。因此只需要 $c$ 步即可，其中 $c$ 表示序列中大于 $1$ 的数有几个。
剩下的情况就是：序列的最大公约数为 $1$，但是每个元素都大于 $1$。如果我们能通过某种方式把第一个 $1$ 弄出来，就转化为了上述第二种特殊情况，答案就是“弄出第一个 $1$ 的最少步数”，加上“弄出第一个 $1$ 后，序列里大于 $1$ 的数还有几个”。第二项的值显然是 $(n - 1)$，因此剩下的问题就是计算“弄出第一个 $1$ 的最少步数”。
首先注意到一个关键结论：进行任意次操作之后，序列里的第 $i$ 个数一定是 $\text{gcd}(a[l..r])$，其中 $a[l..r]$ 表示序列里从第 $l$ 个数到第 $r$ 个数形成的连续子数组，并且满足 $l \le i \le r$。这个结论可以用归纳法进行证明。
既然操作的结果是一段连续子数组的最大公约数，那么对于一个长度为 $k$ 的子数组，我们可以通过 $(k - 1)$ 次操作把其中一个数变成整个子数组的最大公约数。因此，我们只需要找到长度最小的子数组，使得子数组的最大公约数等于 $1$，那么“弄出第一个 $1$ 的最少步数”就是子数组的长度减去一。
因为整个序列的长度只有 $50$，我们完全可以从 $2$ 到 $n$ 枚举 $k$，并检查是否存在长度为 $k$ 的，且最大公约数为 $1$ 的子数组。复杂度 $\mathcal{O}(n^3)$。
参考代码（c++）
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// 剩余情况，枚举子数组的长度 l 和子数组的初始下标 i，检查 a[i..i + l - 1] 的 gcd 是否为 1
for (int l = 2; l <= n; l++) for (int i = 0, j = l - 1; j < n; i++, j++) {
int g = nums[i];
for (int k = i; k <= j; k++) g = gcd(g, nums[k]);
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (g == 1) return l - 1 + n - 1;
}
// 不可能，但是函数的所有 branch 一定要有返回值
assert(false);
return -1;
}
};
我们还可以对以上代码进行优化。主要是针对“寻找最大公约数等于 $1$，且长度最小的子数组”这一部分。如果一个子数组的最大公约数为 $1$，那么包含该子数组的其它子数组最大公约数也等于 $1$，因此这一部分可以使用 two pointers 解决，复杂度降至 $\mathcal{O}(n^2)$。
参考代码（c++）
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// 求 a[L..R] 的 gcd
auto gao = [&](int L, int R) {
int g = 0;
for (int i = L; i <= R; i++) g = gcd(g, nums[i]);
return g;
};
int ans = 1e9;
// 双指针求以 i 为开头的，长度最短的，最大公约数为 1 的子数组
// 这个子数组含 i 不含 j
for (int i = 0, j = 0; i < n; i++) {
while (j < n && gao(i, j - 1) != 1) j++;
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (gao(i, j - 1) == 1) ans = min(ans, j - i - 1 + n - 1);
}
return ans;
}
};
上述求子数组最大公约数的 gao 函数仍然可以优化。由于最大公约数满足结合律，我们可以通过 RMQ 或 线段树 在每次 $\mathcal{O}(\log n)$ 的复杂度下计算子数组的最大公约数，复杂度降至 $\mathcal{O}(n\log n)$。
参考代码（c++）
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// go[id] 是线段树节点 id 代表的区间的 gcd
int go[n * 4 + 10];
// 构建线段树
function<void(int, int, int)> build = [&](int id, int l, int r) {
if (l == r) go[id] = nums[l];
else {
int nxt = id << 1, mid = (l + r) >> 1;
build(nxt, l, mid);
build(nxt | 1, mid + 1, r);
go[id] = gcd(go[nxt], go[nxt | 1]);
}
};
build(1, 0, n - 1);
// 查询 [ql, qr] 区间的 gcd
function<int(int, int, int, int, int)> query = [&](int id, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return go[id];
int nxt = id << 1, mid = (l + r) >> 1;
return gcd(
ql <= mid ? query(nxt, l, mid, ql, qr) : 0,
qr > mid ? query(nxt | 1, mid + 1, r, ql, qr) : 0
);
};
// 求 a[L..R] 的 gcd
auto gao = [&](int L, int R) {
if (L > R) return 0;
return query(1, 0, n - 1, L, R);
};
int ans = 1e9;
// 双指针求以 i 为开头的，长度最短的，最大公约数为 1 的子数组
// 这个子数组含 i 不含 j
for (int i = 0, j = 0; i < n; i++) {
while (j < n && gao(i, j - 1) != 1) j++;
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (gao(i, j - 1) == 1) ans = min(ans, j - i - 1 + n - 1);
}
return ans;
}
};
登录
