class Solution {
public:
int subarrayGCD(vector<int>& nums, int k) {
}
};
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 <= 10001 <= nums[i], k <= 109原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-11-09 14:21:36
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
python3 解法, 执行用时: 136 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-09 14:19:18
class Solution:
def subarrayGCD(self, nums: List[int], k: int) -> int:
'''
暴力求解，
'''
from math import gcd
n, ans = len(nums), 0
for i in range(n):
g = 0
for j in range(i, n):
g = gcd(g, nums[j])
if g % k:
break
if g == k:
ans += 1
return ans