作者推荐

视频算法专题

本博文涉及知识点

数学 数论 调和数

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
$⋮$
1/2^(m-1)+$\cdots$+ 1/2^m < 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;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32

测试用例

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);
	}


}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40

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++**实现。