# 319场周赛 最小公倍数为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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
# 解题思路
数论相关题目。由于序列的长度为1000,所以可以遍历所有的子数组并求解其最小的公倍数。求解两个数(a,b)的最小公倍数,a * b / gcd(a,b)。求解多个数的最小公倍数(a,b,c),可以先求解ab的最小公倍数,再和c求解最小公倍数。这样就可以逐渐维护子数组的最小公倍数,时间复杂度$O(n ^ 2 log (n))$其中log(n)为求解最大公因数的时间复杂度。
code
class Solution {
public:
int subarrayLCM(vector<int>& nums, int k) {
int ans = 0;
for(int i = 0;i < nums.size();i ++)
{
int t = nums[i];
for(int j = i;j < nums.size();j ++)
{
t = t * nums[j] / __gcd(t,nums[j]);
if(t == k ) ans ++;
if(t > k) break;
}
}
return ans;
}
};
标签:周赛,319,nums,公倍数,求解,最小,int,数组
From: https://www.cnblogs.com/huangxk23/p/16888404.html