作者推荐
本博文涉及知识点
数学 数论
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 <= 10
1 <= nums[i] <= 2 * 10
预备知识
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/2 < 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++**实现。