2654. 使数组所有元素变成 1 的最少操作次数

2654.使数组所有元素变成1的最少操作次数

题目描述：

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

• 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

数据范围：

$2\le nums.len \le 50, 1\le nums[i] \le 10^6$

题解：

暴力枚举：

枚举所有的子数组，可以动态的更新子数组的值。可以固定数组的左端点，然后每次移动右端点，得到所有的以左端点开头的子数组 $gcd$ 值。

也可以使用线段树之类：

代码：

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int ans = 1e9;
        int cnt1 = 0;
        for(auto& x: nums) cnt1 += (x == 1);
        if(cnt1 != 0) return n - cnt1;
        for(int i = 0; i < n; ++i) {
            int tmp = nums[i];
            for(int j = i; j < n; ++j) {
                tmp = __gcd(tmp, nums[j]);
                if(tmp == 1)
                {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }
        if(ans == 1e9) return -1;
        return n - 2 + ans;
    }
};