【动态规划】最小公倍数为 K 的子数组数目【力扣第 319 场周赛】

题目

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 <= 1000
• 1 <= nums[i], k <= 1000

解题

方法一：动态规划

思路

和 【暴力, 枚举】最大公因数等于 K 的子数组数目【力扣第 316 场周赛】差不多。

对任意两数 $a, b$ 有 $a \times b = gcd(a, b) \times lcm(a, b)$ ，所以 $lcm(a, b) = \frac{a \times b}{gcd(a, b)}$。

动态规划：

• 状态定义：$dp[i][j]$ 表示子数组 $nums[i \dots j]$ 的最小公倍数。
• 状态转移方程：$dp[i][j] = lcm(dp[i][j - 1], nums[j])$。
• 只有一个元素的子数组最小公倍数为他自身，所以 $dp[i][i] = nums[i] (i \in [0, nums.length - 1])$。

最后统计 dp 中有多少等于 k 的数即可。

代码

class Solution {
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    
    public int subarrayLCM(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) dp[i][i] = nums[i];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                dp[i][j] = lcm(dp[i][j - 1], nums[j]);
            }
        }
        for (int[] arr : dp) {
            for (int x : arr) {
                if (x == k) ++ans;
            }
        }
        return ans;
    }
}