2470-最小公倍数为 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 _元素最小公倍数为k _的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

示例 1 ：

**输入：** nums = [3,6,2,7,1], k = 6
**输出：** 4
**解释：** 以 6 为最小公倍数的子数组是：
- [ _ **3**_ , _ **6**_ ,2,7,1]
- [ _ **3**_ , _ **6**_ , _ **2**_ ,7,1]
- [3, _ **6**_ ,2,7,1]
- [3, _ **6**_ , _ **2**_ ,7,1]

示例 2 ：

**输入：** nums = [3], k = 2
**输出：** 0
**解释：** 不存在以 2 为最小公倍数的子数组。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 1000

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

思路和 2447. 最大公因数等于 K 的子数组数目 完全一致。

方法一：暴力枚举

[sol1-Python3]

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            res = 1
            for j in range(i, n):
                res = lcm(res, nums[j])
                if k % res: break  # 剪枝：LCM 必须是 k 的因子
                if res == k: ans += 1
        return ans

[sol1-Go]

func subarrayLCM(nums []int, k int) (ans int) {
	for i := range nums {
		lcm := 1
		for _, x := range nums[i:] {
			lcm = lcm / gcd(lcm, x) * x
			if k%lcm > 0 { // 剪枝：lcm 必须是 k 的因子
				break
			}
			if lcm == k {
				ans++
			}
		}
	}
	return
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

复杂度分析

• 时间复杂度：O(n(n+\log k))，其中 n 为 nums 的长度。LCM 倍增的次数是 O(\log k) 次，因此内层循环的时间复杂度为 O(n+\log k)，所以总的时间复杂度为 O(n(n+\log k))。
• 空间复杂度：O(1)，仅用到若干变量。

方法二：利用 LCM 的性质

参考我之前的那篇 题解 。

最小公倍数要么不变，要么至少 \times 2，因此在遍历 nums 的同时，维护最小公倍数集合（数组），这至多有 O(\log k) 个。

注意最小公倍数必须是 k 的因子。

[sol2-Python3]

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        ans = 0
        a = []  # [LCM，相同 LCM 区间的右端点]
        i0 = -1
        for i, x in enumerate(nums):
            if k % x:  # 保证后续求的 LCM 都是 k 的因子
                a = []
                i0 = i
                continue
            a.append([x, i])
            # 原地去重，因为相同的 LCM 都相邻在一起
            j = 0
            for p in a:
                p[0] = lcm(p[0], x)
                if a[j][0] != p[0]:
                    j += 1
                    a[j] = p
                else:
                    a[j][1] = p[1]
            del a[j + 1:]
            if a[0][0] == k:
                ans += a[0][1] - i0
        return ans

[sol2-Go]

func subarrayLCM(nums []int, k int) (ans int) {
	type result struct{ lcm, i int }
	var a []result
	i0 := -1
	for i, x := range nums {
		if k%x > 0 {
			a = nil
			i0 = i
			continue
		}
		for j, p := range a {
			a[j].lcm = p.lcm / gcd(p.lcm, x) * x
		}
		a = append(a, result{x, i})
		j := 0
		for _, q := range a[1:] {
			if a[j].lcm != q.lcm {
				j++
				a[j] = q
			} else {
				a[j].i = q.i
			}
		}
		a = a[:j+1]
		if a[0].lcm == k {
			ans += a[0].i - i0
		}
	}
	return
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

复杂度分析

• 时间复杂度：O(n\log k)，其中 n 为 nums 的长度。LCM 倍增的次数是 O(\log k) 次，并且每次去重的时间复杂度也为 O(\log k)，因此时间复杂度为 O(n\log k)。
• 空间复杂度：O(\log k)。