难度: Medium
给你一个整数数组 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 <= 10001 <= nums[i], k <= 1000运行时间: 33 ms
内存: 16.4 MB
class Solution:
def subarrayLCM(self, nums: List[int], k: int) -> int:
ans = 0
a = []
o = -1
for i, x in enumerate(nums):
if k % x:
a = []
o = i
continue
a.append([x, i])
j = 0
for p in a:
p[0] = lcm(p[0], x)
print(j)
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] - o
return ans
此题解采用动态维护数组内元素的最小公倍数（LCM）的思路。遍历数组时，只考虑那些能够被k整除的元素，因为如果元素x不能被k整除，则任何包含x的子数组的最小公倍数也不能为k。对于能被k整除的元素，使用一个辅助数组a来存储当前考虑的子数组的元素及其索引。每次遇到一个新元素，计算它与a中已有元素的LCM，并更新a。如果a的第一个元素的LCM等于k，则统计以该元素结尾的符合条件的子数组数量。如果遇到不能被k整除的元素，则重置a数组，重新开始统计。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def subarrayLCM(self, nums: List[int], k: int) -> int:
ans = 0 # 用于记录满足条件的子数组数量
a = [] # 存储当前考虑的元素及其索引
o = -1 # 最近一个不能被 k 整除的元素的索引
for i, x in enumerate(nums):
if k % x: # 如果 x 不能被 k 整除
a = [] # 重置 a
o = i # 更新 o 为当前索引
continue
a.append([x, i]) # 将当前元素及索引添加到 a
j = 0
for p in a: # 更新 a 中每个元素的 LCM
p[0] = lcm(p[0], x)
if a[j][0] == p[0]:
a[j][1] = p[1]
del a[j + 1:] # 删除多余的元素
if a[0][0] == k: # 如果找到了一个有效的子数组
ans += a[0][1] - o # 计算子数组数量
return ans
为了确保计算最小公倍数（LCM）的效率和正确性，可以利用最大公约数（GCD）来进行计算。最小公倍数LCM可以通过公式 LCM(a, b) = |a * b| / GCD(a, b) 来计算。这种方法首先使用辗转相除法（Euclid's algorithm）来找到两个数的最大公约数，然后用两数乘积除以最大公约数得到最小公倍数。这种方法在数学上是精确的，并且在算法实现上也是高效的，因为GCD的计算是对数时间复杂度。
在遇到不能被k整除的元素时，需要重置辅助数组a，并更新索引o，是因为任何包含这个元素的子数组的最小公倍数都不可能是k。因此，从该元素之后重新开始寻找新的子数组，是必要的。将o设置为当前元素索引，是为了在找到满足条件的子数组时，能够正确计算从上一个不能被k整除的元素之后到当前元素为止的子数组数量。这样可以保证所有可能的子数组都被考虑到，同时避免包含无效元素影响结果的准确性。
如果a的第一个元素的LCM恰好等于k，那么从上一个不能被k整除的元素后的位置到当前位置的所有子数组都将是符合条件的。因为这些子数组的LCM将由连续的、可以被k整除的元素组成，且没有其他元素影响这个LCM的值。这种方法理论上能覆盖所有符合条件的子数组，不会遗漏。但这前提是算法必须正确维护LCM的值，且逻辑上没有错误。在实际实现时，需要注意细节处理，以确保每个符合条件的子数组都被正确统计。
在题解中，当添加新元素x到辅助数组a时，会更新每个元素的LCM值。如果在更新过程中，某个元素的LCM值与后来的LCM值相同，则意味着该元素以及之前的所有元素可以被更精简的表示。因此，维持这个最小集合的元素是必要的，其他的元素则被认为是多余的。这样做可以减少之后操作的复杂度，确保数组a只保留最关键的信息，即每个不同LCM值的起始位置。