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

链接：2470.最小公倍数为K的子数组数目
难度：Medium
标签：数组、数学、数论
简介：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

题解 1 - cpp

• 编辑时间：2022-11-13
• 执行用时：20ms
• 内存消耗：9MB
• 编程语言：cpp
• 解法介绍：遍历，对每个子数组找最小公倍数。

class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int subarrayLCM(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int cur_gcd = nums[i], num = nums[i];
            for (int j = i; j < n; j++) {
                num = num * nums[j] / gcd(num, nums[j]);
                if (num == k) ans++;
                if (num > k) break;
            }
        }
        return ans;
    }
};