[LeetCode] LCP 14. 切分数组-一一网

? “Offer 驾到，掘友接招！我正在参与2022春招打卡活动点击查看活动详情。

LCP 14. 切分数组

题目描述

给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。

示例 1:

输入：nums = [2,3,3,2,3,3]
输出：2
解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。
复制代码

示例 2:

输入：nums = [2,3,5,7]
输出：4
解释：只有一种可行的切割：[2], [3], [5], [7]
复制代码

限制：

1 <= nums.length <= 10^5
2 <= nums[i] <= 10^6

解题思路：

先预处理出 1000000 以内的所有素数，使用欧拉筛
使用 f[i][x]记录已处理的前 i个数中，所有能被素数 x 整除的数之前（不包含其自身）的所有数字最少可以划分成的段数。使用g[i]记录前 i 个数可以被划分的最少段数，则:

$f[i][p]=min(f[i-1][p] +1,g[i-1]+1),p为k的所有素数因子$

$g[i]=min(g[i-1],min(f[i-1][p]+1)),p为k的所有素数因子$
考虑到素数的离散分布，以及 g[i]只依赖于 f[i-1]和g[i-1]，实现时f[i]可以使用哈希表
并且可以通过先处理 g[i]，再更新f的方式来降维

代码如下：

#预处理
N = 1000001
primes, isp = [], [True] * N
isp[0] = isp[1] = False
for i in range(2, N):
    if isp[i]:
        primes.append(i)
    for p in primes:
        if (ii := i * p) >= N:
            break
        isp[ii] = False
        if i % p == 0:
            break

class Solution:
    def splitArray(self, nums: List[int]) -> int:
        f = defaultdict(lambda:sys.maxsize)
        pre = 0
        for x in nums:
            cur = pre + 1
            if isp[x]:
                cur = min(f[x] + 1, cur)
                f[x] = min(f[x], pre)
            else:
                for p in primes:
                    a, b = divmod(x, p)
                    if b == 0:
                        if p in f:
                            cur = min(f[p] + 1, cur)
                        if isp[a]:
                            cur = min(f[a] + 1, cur) # ㈠
                        f[p] = min(f[p], pre)
                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止
                            f[a] = min(f[a], pre)
                            break
                    if p * p >= x:
                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到
                        # 这样可以大量减少无效遍历
                        break
            pre = cur
        return pre

复制代码