分割数组使乘积互质

题目

2584. 分割数组使乘积互质

---

给你一个长度为 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：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 10^4
• 1 <= nums[i] <= 10^6

题解

方法一：

思路

对于某个质因子在nums中出现的最早的位置l和最晚的位置r。
我们的答案不能出现在[l,r)间。

我们找出所有质因子的分布区间，找到最早的一个不在这些区间的点即可。可以用差分数组做区间修改，最后统计每个点覆盖的次数即可，当出现没有覆盖的位置则存在答案。

代码

class Solution {
public:
    #define N 1000005
    int mpf[N];//mpf[i] i的 min prime factor
    void getmpf() {//获取N以内所有数的最小质因子
        memset(mpf, 0, sizeof(mpf));
        int sz = sqrt(N);
        for (int i=2; i<=sz; i++) {
            if (mpf[i]) continue;
            for (int j=i*i; j<N; j+=i) {
                mpf[j] = i;
            }
        }
        for (int i=2; i<N; i++) {
            if (mpf[i] == 0) mpf[i] = i;//质数的最小质因子是本身
        }
        // for (int i=0; i<N; i++) {
        //     cout << i << "=" << mpf[i] << ", ";
        // }
    }


    int findValidSplit(vector<int>& nums) {
        getmpf();
        int n = nums.size();
        map<int,pair<int,int>> mp;
        for (int j=0; j<n; j++) {
            int x = nums[j];
            for (int i=x; i>1; i = i/mpf[i]) {
                // cout << mpf[i] << " ";
                if (!mp.count(mpf[i])) mp[mpf[i]] = {n+1, -1};
                mp[mpf[i]].first = min(mp[mpf[i]].first, j);
                mp[mpf[i]].second = max(mp[mpf[i]].second, j);
            }
        }
        vector<int> d(n+1, 0);
        for (auto [i,j]:mp) {
            d[j.first]++;
            d[j.second]--;
            // cout << i << endl;
            // cout << j.first << " " << j.second << endl;
        }
        int p = 0;
        for (int i=0; i<n-1; i++) {
            p += d[i];
            if (p == 0) return i;
        }
        return -1;
    }
};