【C++数论】2447. 最大公因数等于 K 的子数组数目|1602
本文涉及知识点
LeetCode2447. 最大公因数等于 K 的子数组数目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
子数组 是数组中一个连续的非空序列。
数组的最大公因数 是能整除数组中所有元素的最大整数。
示例 1：
输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
示例 2：
输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。
提示：
1 <= nums.length <= 1000
1 <= nums[i], k <= 109
数论
nums[j…i]的最大公约数最多log(nums[i])个，
tmp[j] 记录nums[j…i]的最大公约数，则tmp单调递增。扣掉重复元素，tmp最多log(nums[i])个元素，因为：tmp[i+1]至少是tmp[i]的两倍。
pre记录 tmp[j]非重复元素，重复元素取下标最大的。及值。
cur各元素 = gcd(pre的质，nums[i])
cur增加nums[i]
cur增加的时候出重。
代码
核心代码
class Solution {
public:
int subarrayGCD(vector<int>& nums, int k) {
int ans = 0;
vector<pair<int, int>> pre;
for (int i = 0; i < nums.size(); i++) {
const int& n = nums[i];
vector<pair<int, int>> dp;
for (const auto& [p, j] : pre) {
const int iNew = gcd(p, n);
if (dp.empty() || (dp.back().first != iNew)) {
dp.emplace_back(iNew, j);
}
}
if (dp.empty() || (dp.back().first != n)) {
dp.emplace_back(n, i);
};
for (int j = 0; j + 1 < dp.size(); j++) {
if (dp[j].first == k) {
ans += dp[j + 1].second - dp[j].second;
}
}
if (dp.back().first == k) { ans += i - dp.back().second + 1; }
pre.swap(dp);
}
return ans;
}
};
单元测试
vector<int> nums;
int k;
TEST_METHOD(TestMethod11)
{
nums = { 9, 3, 1, 2, 6, 3 }, k = 3;
auto res = Solution().subarrayGCD(nums, k);
AssertEx(4, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 4 }, k = 7;
auto res = Solution().subarrayGCD(nums, k);
AssertEx(0, res);
}
TEST_METHOD(TestMethod13)
{
nums = { 3,3,4,1,2 }, k = 1;
auto res = Solution().subarrayGCD(nums, k);
AssertEx(10, res);
}
TEST_METHOD(TestMethod14)
{
nums = { 1000000000 }, k = 1;
auto res = Solution().subarrayGCD(nums, k);
AssertEx(0, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/142978190
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！