本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode2470. 最小公倍数等于 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

数论

注意：lcm nums的结果可能远超过unit64。一个元素大于k后，就不用计算了，最小公约数铁定不是k。由于cur是降序，cur[i].first==k，最小公倍数为k且以nums[j]结尾的数量为：cur[i+1].second - cur[i].first。
cur = dp[i] 记录nums[j…i]的最小公倍数，及最大下标j。如果最小公倍数大于k。无需计算。 重复元素需要记录最大下标。显然下标越小，公倍数越大，最多logk个。大的至少是小的2倍。
pre = dp[i-1]
cur 等于 lcm(pre各元素,nums[i])
cur.add(nums[i],i)
注意：出重及忽略大于k的最小公倍数。

改进版

cur各元素记录{最小公倍数,数量}

代码

核心代码

class Solution {
		public:
			int subarrayLCM(vector<int>& nums, int k) {
				int ans = 0;
				vector<pair<int, int>> pre;
				for (const auto& n : nums) {
					vector<pair<int, int>> dp;
					auto Add = [&](int iNew, int c) {
						if (iNew > k) { return; }
						if (iNew == k) { ans += c; }
						if (dp.size() && (dp.back().first == iNew)) {
							dp.back().second += c;
						}
						else {
							dp.emplace_back(iNew, c);
						}
					};
					for (const auto& [p, c] : pre) {
						const int iNew = lcm(p, n);
						Add(iNew, c);
					}
					Add(n, 1);
					pre.swap(dp);
				}
				return ans;
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 3,6,2,7,1 }, k = 6;
			auto res = Solution().subarrayLCM(nums, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 3 }, k = 2;
			auto res = Solution().subarrayLCM(nums, k);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 773,613,11,8,103 }, k = 40;
			auto res = Solution().subarrayLCM(nums, k);
			AssertEx(0, res);
		}