# 2584.分割数组使乘积互质 (Medium)

## 问题描述
[2584. 分割数组使乘积互质 (Medium)](https://leetcode.cn/problems/split-the-array-to-make-coprime-products/)

给你一个长度为 `n` 的整数数组 `nums` ，下标从 **0** 开始。

如果在下标 `i` 处 **分割** 数组，其中 `0 <= i <= n - 2` ，使前 `i + 1`
个元素的乘积和剩余元素的乘积互质，则认为该分割 **有效** 。

- 例如，如果 `nums = [2, 3, 3]` ，那么在下标 `i = 0` 处的分割有效，因为 `2` 和
`9` 互质，而在下标 `i = 1` 处的分割无效，因为 `6` 和 `3` 不互质。在下标 `i = 2`
处的分割也无效，因为 `i == n - 1` 。

返回可以有效分割数组的最小下标 `i` ，如果不存在有效分割，则返回 `-1` 。

当且仅当 `gcd(val1, val2) == 1` 成立时， `val1` 和 `val2`
这两个值才是互质的，其中 `gcd(val1, val2)` 表示 `val1` 和 `val2` 的最大公约数。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065608.png)

```
输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。
```

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065609.png)

```
输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。

```

**提示：**

- `n == nums.length`
- `1 <= n <= 10⁴`
- `1 <= nums[i] <= 10⁶`

## 解题思路
分割数组使乘积互质，本质上是让左半边和右半边的数所包含的质因子互不相同。考虑质因子$i$，即求质因子包含$i$的最左边的数和最右边的数的索引，然后转化为区间重叠问题；

这里要注意质因子的$O(\log n)$求法，可参照[C++质因子分解](https://blog.zwyyy456.tech/zh/posts/tech/prime_factorization/)

## 代码
```cpp
class Solution {
  public:
    void get_range(int fac, int idx, unordered_map<int, pair<int, int>> &factor_range) {
        if (factor_range.find(fac) != factor_range.end()) {
            factor_range[fac].second = idx;
        } else {
            factor_range[fac] = {idx, idx};
        }
    }
    int findValidSplit(vector<int> &nums) {
        if (nums.size() < 2)
            return -1;
        unordered_map<int, pair<int, int>> factor_range;
        for (int i = 0; i < nums.size(); ++i) {
            for (int fac = 2; fac * fac <= nums[i]; fac++) {
                if (nums[i] % fac == 0) {
                    while (nums[i] % fac == 0) {
                        nums[i] /= fac;
                    }
                    get_range(fac, i, factor_range);
                }
            }
            if (nums[i] > 1) { // 说明nums[i]本身是质数
                get_range(nums[i], i, factor_range);
            }
        }
        vector<pair<int, int>> factors;
        factors.reserve(factor_range.size());
        for (auto &range : factor_range) {
            factors.push_back(range.second);
        }
        std::sort(factors.begin(), factors.end());
        int left = factors[0].first;
        int right = factors[0].second;
        for (int i = 1; i < factors.size(); i++) {
            if (factors[i].first > right) {
                return factors[i].first - 1;
            } else {
                right = std::max(factors[i].second, right);
            }
        }
        return -1;
    }
};
```