[leetcode]2584.分割数组使乘积互质（质因数分解）xiaodangao

题目链接：分割数组使乘积互质
思路：指针循环从 $[0,len-1)$ 每次动态维护指针左边所有数与指针右边所有数质因数交集，第一次交集为0的地方为答案。首先将打表 $10^6$ 之内的质数，这样质因数分解快一些。
$Code:$

class Solution {
public:
    #define ll long long
    #define pb push_back 
    const int N = 1e6 + 10;
int tot;
int prime[1000010];
bool st[1000010];
void get_it() {
    for (int i = 2; i <= 1000000; ++i) {
        if (st[i]) continue;
        prime[++tot] = i;
        if (i >= 10000) continue;
        for (int j = i * i; j <= 1000000; j += i) { st[j] = true; }
    }
}
int cnt[1000010];
vector<int> arr[10100];
void work(int x, int id) {
    int i = 1;
    while (prime[i] * prime[i] <= x) {
        if (x % prime[i] == 0) {
            while (x % prime[i] == 0) x /= prime[i];
            cnt[prime[i]]++;
            arr[id].pb(prime[i]);
        }
        i++;
    }
    if (x != 1) {
        cnt[x]++;
        arr[id].pb(x);
    }
}
int res = 0;

int findValidSplit(vector<int>& nums) {
    get_it();
    int id = 0;
    for (auto i : nums) { work(i, id++); }
    memset(st, 0, sizeof st);
    int len = nums.size();
    if (len == 1) return -1;
    for (int i = 0; i < len - 1; ++i) {
        for (auto j : arr[i]) {
            cnt[j]--;
            if (cnt[j] == 0) {
                if(st[j]){
                    res--;
                }
            } else if (!st[j]) {
                res++;
            }
            st[j] = true;
        }
        if (res == 0) return i;
    }
    return -1;
}
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。