2447-最大公因数等于 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

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

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

**输入：** nums = [9,3,1,2,6,3], k = 3
**输出：** 4
**解释：** nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9, ** _3_** ,1,2,6,3]
- [9,3,1,2,6, _ **3**_ ]
- [ ** _9,3_** ,1,2,6,3]
- [9,3,1,2, _ **6,3**_ ]

示例 2：

**输入：** nums = [4], k = 7
**输出：** 0
**解释：** 不存在以 7 作为最大公因数的子数组。

提示：

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

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

---

方法一：暴力枚举

暴力枚举即可，可以在不包含因子 k 时提前退出循环。

[sol1-Python3]

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(len(nums)):
            g = 0
            for j in range(i, len(nums)):
                g = gcd(g, nums[j])
                if g % k: break
                if g == k: ans += 1
        return ans

[sol1-Go]

func subarrayGCD(nums []int, k int) (ans int) {
	for i := range nums {
		g := 0
		for _, x := range nums[i:] {
			g = gcd(g, x)
			if g%k > 0 {
				break
			}
			if g == k {
				ans++
			}
		}
	}
	return
}

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

复杂度分析

• 时间复杂度：O(n(n+\log U))，其中 n 为 nums 的长度，U=max(\textit{nums})。外层循环时，单看 g=\textit{nums}[i]，它因为求 GCD 减半的次数是 O(\log U) 次，因此内层循环的时间复杂度为 O(n+\log U)，所以总的时间复杂度为 O(n(n+\log U))。
• 空间复杂度：O(1)，仅用到若干变量。

方法二：利用 GCD 的性质

原理见我之前写的 这篇题解的方法二 ，视频讲解 详细介绍了这种算法的原理。

[sol1-Python3]

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        ans = 0
        a = []  # [GCD，相同 GCD 区间的右端点]
        i0 = -1
        for i, x in enumerate(nums):
            if x % k:  # 保证后续求的 GCD 都是 k 的倍数
                a = []
                i0 = i
                continue
            a.append([x, i])
            # 原地去重，因为相同的 GCD 都相邻在一起
            j = 0
            for p in a:
                p[0] = gcd(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:  # a[0][0] >= k
                ans += a[0][1] - i0
        return ans

[sol1-Go]

func subarrayGCD(nums []int, k int) (ans int) {
	type result struct{ v, i int }
	var a []result
	i0 := -1
	for i, v := range nums {
		if v%k > 0 {
			a = nil
			i0 = i
			continue
		}
		for j, p := range a {
			a[j].v = gcd(p.v, v)
		}
		a = append(a, result{v, i})
		j := 0
		for _, q := range a[1:] {
			if a[j].v != q.v {
				j++
				a[j] = q
			} else {
				a[j].i = q.i
			}
		}
		a = a[:j+1]
		if a[0].v == 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 U)，其中 n 为 nums 的长度，U=max(\textit{nums})。单看每个元素，它因为求 GCD 减半的次数是 O(\log U) 次，并且每次去重的时间复杂度也为 O(\log U)，因此时间复杂度为 O(n\log U)。
• 空间复杂度：O(\log U)。

相似题目

• Codeforces 475D. CGCDSSQ