class Solution {
public:
int subarrayLCM(vector<int>& nums, int k) {
}
};
6234. 最小公倍数为 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 <= 10001 <= nums[i], k <= 1000原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-14 15:07:41
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
}
for len(a) > 0 && k%a[0].lcm > 0 { // 去除不合法的 LCM
a = a[1:]
}
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
}
golang 解法, 执行用时: 24 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-14 15:04:36
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
}
python3 解法, 执行用时: 292 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-14 15:03:31
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