2584：分割数组使乘积互质（2159 分）

Ian

2023-03-05 约 854 字预计阅读 2 分钟次阅读

力扣第 335 场周赛第 3 题

题目

给你一个长度为 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⁴
1 <= nums[i] <= 10⁶

分析

先考虑 nums[0]：

对于 nums[0] 的某个因数 p，如果 nums[j] 也有因数 p，那么分割点必须在 j 之后
找出 nums[0] 所有因数存在的最靠后的下标 r
假如 r==0，那么分割点即是 0
否则，[0,r] 必须分割到一起，要继续遍历

接着考虑 nums[1]：

同理，找出所有因数存在的最靠后的下标 r2，更新 r=max(r,r2)
如果 r==1，分割点即是 1。否则，继续遍历

因此，找出 nums 每个元素的素因数，并得到每个素因数存在的最靠后的下标，即可遍历解决。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


def findValidSplit(self, nums: List[int]) -> int:
	@cache
	def factor(x):
		vis = set()
		for p in chain([2],range(3,isqrt(x)+1,2)):
			if x%p==0:
				vis.add(p)
				while x%p==0:
					x //= p
		if x>1:
			vis.add(x)
		return vis

	d, n = {}, len(nums)
	for i in range(n):
		for p in factor(nums[i]):
			d[p] = i
	r = 0
	for i in range(n-1):
		for p in factor(nums[i]):
			r = max(r,d[p])
		if r==i:
			return i
	return -1

936 ms

*附加

还可以借助埃氏筛法先获得数据范围内的质数列表，加快元素的质因数分解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


def findValidSplit(self, nums: List[int]) -> int:
	def get_primes(M):
		f = [1]*M
		for i in range(2,isqrt(M)+1):
			if f[i]:
				f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
		return [i for i in range(2,M) if f[i]]

	@cache
	def factor(x):
		vis = set()
		for p in primes:
			if x%p==0:
				vis.add(p)
				while x%p==0:
					x //= p
		if x>1:
			vis.add(x)
		return vis

	primes = get_primes(isqrt(max(nums))+1)
	d, n = {}, len(nums)
	for i in range(n):
		for p in factor(nums[i]):
			d[p] = i
	r = 0
	for i in range(n-1):
		for p in factor(nums[i]):
			r = max(r,d[p])
		if r==i:
			return i
	return -1

396 ms

目录

2584：分割数组使乘积互质（2159 分）

题目

分析

解答

*附加