侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-13 / 0 评论 / 1 点赞 / 60 阅读 / 588 字 / 正在检测是否收录...

题目

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,ba, ba×b=gcd(a,b)×lcm(a,b)a \times b = gcd(a, b) \times lcm(a, b) ,所以 lcm(a,b)=a×bgcd(a,b)lcm(a, b) = \frac{a \times b}{gcd(a, b)}

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示子数组 nums[ij]nums[i \dots j] 的最小公倍数。
  • 状态转移方程:dp[i][j]=lcm(dp[i][j1],nums[j])dp[i][j] = lcm(dp[i][j - 1], nums[j])
  • 只有一个元素的子数组最小公倍数为他自身,所以 dp[i][i]=nums[i](i[0,nums.length1])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;
    }
}
1

评论区