LC 2584. 分割数组使乘积互质

https://leetcode.cn/contest/weekly-contest-335/problems/split-the-array-to-make-coprime-products/

这题最粗俗的解法就是分解因子，然后记录每个位置上可能的因子个数，然后不断往前推，使得某个点上所有因子的个数都涵盖到了。

我看了这个解法觉得特别有意思 https://leetcode.cn/problems/split-the-array-to-make-coprime-products/solution/ben-zhi-shi-tiao-yue-you-xi-by-endlessch-8chd/

大致思想是，记录每个位置上这个数，它所有的可能因子最远距离。一旦我选择了这个数，那么我就需要选择这个因子，那么就必须跳跃到这个因子的最远位置。

这里面数据结构也非常有意义： 

from typing import List


def get_primes(M):
    P = [0] * (M + 1)
    for i in range(2, M + 1):
        if P[i] == 1: continue
        for j in range(2, M + 1):
            if i * j > M: break
            P[i * j] = 1

    primes = []
    for i in range(2, M + 1):
        if P[i] == 0:
            primes.append(i)

    return primes


class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        M = min(max(nums), 10 ** 3)
        primes = get_primes(M)
        left = {}
        right = [0] * (len(nums))

        def update(p, idx):
            if p not in left:
                pos = idx
                left[p] = idx
            else:
                pos = left[p]
            right[pos] = idx

        for idx, x in enumerate(nums):
            for p in primes:
                if x % p == 0:
                    while x % p == 0:
                        x = x // p
                    update(p, idx)
            if x > 1:
                update(x, idx)

        ans = 0 # 假设当前最远位置
        for idx, r in enumerate(right):
            if idx > ans:
                return ans
            ans = max(ans, r)
        return -1