本博文涉及知识点
数学 数论
LeetCode1819. 序列中不同最大公约数的数目
给你一个由正整数组成的数组 nums 。
数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。
例如，序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。
例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。
示例 1：
输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。
示例 2：
输入：nums = [5,15,40,5,6]
输出：7
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105
预备知识
1+1/2 + 1/3 +1/4 ⋯ \cdots⋯ 1/ n 约等于 logn。
证明过程：
1/3 + 1/4 < 1
1/5 + 1/6 + 1/7 + 1/8 < 1
1/9+1/10+…1/16 < 1
⋮ \vdots⋮
1/2^(m-1)+⋯ \cdots⋯+ 1/2m < 1
数论
vNum[i]表示i在nums中出现过。
vCnt[i]记录i的倍数在vNum[i]中出现的次数。
vCnt[i]如果等于0，则不是子序列的最大公约数。
{4,8} vCnt[2]==2,但不存在子序列的公约数为2。
vCnt[i] == vCnt[j]，如果i是j的因子，则不存在公约数为i。
代码
class Solution { public: int countDifferentSubsequenceGCDs(vector<int>& nums) { const int iMax = *std::max_element(nums.begin(), nums.end()); vector<bool> vNum(iMax + 1); for (const auto& n : nums) { vNum[n] = true; } vector<int> vCnt(iMax + 1); for (int i = 1; i <= iMax; i++) { for (int j = i; j <= iMax; j+=i) { vCnt[i] += vNum[j]; } } int ans = 0; for (int i = 1; i <= iMax; i++) { for (int j = i*2; j <= iMax; j += i) { if (vCnt[i] == vCnt[j]) { vCnt[i] = 0; } } ans += (vCnt[i] > 0); } return ans; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; { Solution sln; nums = { 6, 10, 3 }; auto res = sln.countDifferentSubsequenceGCDs(nums); Assert(5, res); } { Solution sln; nums = { 5, 15, 40, 5, 6 }; auto res = sln.countDifferentSubsequenceGCDs(nums); Assert(7, res); } }
2023年5月
class Solution { public: int countDifferentSubsequenceGCDs(vector& nums) { int iMax = *std::max_element(nums.begin(), nums.end()); vector vHas(iMax + 1); for (const auto& n : nums) { vHas[n] = true; } int iRet = 0; for (int i = 1; i <= iMax; i++) { if (vHas[i]) { iRet ++ ; continue; } int iGCD = 0; for (int j = i * 2; j <= iMax; j += i) { if (!vHas[j]) { continue; } if (0 == iGCD) { iGCD = j; } else { iGCD = GCD(iGCD, j); if (i == iGCD) { iRet++; break; } } } } return iRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
