【最大公约数唯一分解定理调和级数】2862. 完全子集的最大元素和

本文涉及知识点

质数、最大公约数、菲蜀定理
组合数学汇总
唯一分解定理调和级数

LeetCode2862. 完全子集的最大元素和

给你一个下标从 1 开始、由 n 个整数组成的数组。你需要从 nums 选择一个完全集，其中每对元素下标的乘积都是一个
完全平方数，例如选择 ai 和 aj ，i * j 一定是完全平方数。
返回完全子集所能取到的最大元素和。
示例 1：
输入：nums = [8,7,3,5,7,2,4,9]
输出：16
解释：我们选择了下标 1 和 4 的元素，并且 1 * 4 是一个完全平方数。
示例 2：
输入：nums = [8,10,3,8,1,13,7,9,4]
输出：20
解释：我们选择了下标 1，4 和 9 的元素。1 * 4，1 * 9，4 * 9 都是完全平方数。

提示：
1 <= n == nums.length <= 10⁴
1 <= nums[i] <= 10⁹

最大公约数

性质一：通过唯一分解定理将x分解为： a1ⁱ¹a2ⁱ² $\cdots$ 。x是完全平方数 $\iff$ i1 i2 $\cdots$ 全部是偶数。证明：
y=a1^i1/2 $\times$ a2^i2/2 $\times \cdots$ ,则y $\times$ y = x。

假定n = nums.size()无限大

某个完全子集的在nums中的下标分别为：{i1,i2 $\cdots$ im}
假定其最大公约数为q，则{i1 $\div$ q,i2 $\div$ q, $\cdots$ } 也是完全子集。
令j1 =i1 $\div$ q,j2 =i2 $\div$ q $\cdots$ 。
S={j1,j2 $\cdots$ jm} 乘以任意正正数仍然是完全子集。
性质二此时S中的元素全部是平方数。由于任意两个元素x1,x2互质，故他们没有公因数。x1 $\times$ x2的任意公因数y 要么全部出现在x1，要么全部出现在x2,不失一般性，假定出现在x1中。由于x1 $\times$ x2是完全平方数，故y1出现的次数是偶数。即在x1中出现偶数次，在x2中出现0次,0次也是偶数次。
性质三：如果S的最大值是jm，则S包括[1,jm]任然是完全子集。
结论：任意完全子集的下标一定是：{x,4x,9x,16x $\cdots$ }

枚举完全子集小标的最大公约数

核心代码

class Solution {
public:
	long long maximumSum(vector<int>& nums) {
		m_c = nums.size();
		long long llRet = 0;
		for (int q = 1; q <= m_c; q++) {
			long long llSum = 0;
			for (long long i = 1; i * i * q <= m_c; i++) {
				llSum += nums[i * i * q - 1];
			}
			llRet = max(llRet, llSum);
		}
		return llRet;
	}
	int m_c;
};

测试用例

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

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<int> nums;
	{
		Solution slu;
		nums = { 8,7,3,5,7,2,4,9 };
		auto res = slu.maximumSum(nums);
		Assert(16LL, res);
	}
	{
		Solution slu;
		nums = { 8,10,3,8,1,13,7,9,4 };
		auto res = slu.maximumSum(nums);
		Assert(20LL, res);
	}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛