跳转至

2470. 最小公倍数等于 K 的子数组数目

来源第 319 场周赛 Q2难度中等分数1559

题目描述

给你一个整数数组 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

解法

方法一：枚举

思考

\(n \le 1000\)，可以从每个左端点向右扫描。某个元素不能整除 \(k\) 时，包含它的连续段的最小公倍数也不可能是 \(k\)，因此立刻停止。停止之前，运行中的最小公倍数始终整除 \(k\)，从而不超过 \(k\)。若先把两数相乘再除以最大公约数， \(a \times b\) 会在真正的最小公倍数仍不超过 \(2^{31}-1\) 时溢出，把本不是 \(k\) 的段误判为答案。

枚举每个下标作为左端点并向右延伸。遇到不能整除 \(k\) 的元素就停止。延伸过程中运行的最小公倍数始终整除 \(k\)，等于 \(k\) 时答案加一。

时间复杂度 \(O(n^2)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from math import lcm


class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(len(nums)):
            a = 1
            for b in nums[i:]:
                if k % b:
                    break
                a = lcm(a, b)
                ans += a == k
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int a = 1;
            for (int j = i; j < nums.length; ++j) {
                if (k % nums[j] != 0) {
                    break;
                }
                a = lcm(a, nums[j]);
                if (a == k) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int a = 1;
            for (int j = i; j < nums.size(); ++j) {
                if (k % nums[j] != 0) {
                    break;
                }
                a = lcm(a, nums[j]);
                ans += a == k;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func subarrayLCM(nums []int, k int) (ans int) {
    for i := range nums {
        a := 1
        for _, b := range nums[i:] {
            if k%b != 0 {
                break
            }
            a = lcm(a, b)
            if a == k {
                ans++
            }
        }
    }
    return
}

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

func lcm(a, b int) int {
    return a / gcd(a, b) * b
}

评论