【最大公约数 唯一分解定理 调和级数】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 <= 104
1 <= nums[i] <= 109

最大公约数

性质一:通过唯一分解定理将x分解为: a1i1a2i2 ⋯ \cdots 。x是完全平方数    ⟺    \iff i1 i2 ⋯ \cdots 全部是偶数。证明:
y=a1i1/2 × \times ×a2i2/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

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/609130.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

程序员学CFA——数量分析方法(六)

数量分析方法&#xff08;六&#xff09; 假设检验假设检验的步骤假设检验的基本思想与步骤估计与假设检验的区别假设检验的基本思想假设检验的步骤 假设检验的相关概念原假设与备择假设检验统计量及其分布显著性水平双尾检验与单尾检验p值第一类错误与第二类错误统计显著与经济…

力扣HOT100 - 155. 最小栈

解题思路&#xff1a; 辅助栈 class MinStack {private Stack<Integer> stack;private Stack<Integer> min_stack;public MinStack() {stack new Stack<>();min_stack new Stack<>();}public void push(int val) {stack.push(val);if (min_stack.i…

SpringBoot集成jxls2实现复杂(多表格)excel导出

核心依赖 需求 导出多个表格&#xff0c;包含图片&#xff0c;类似商品标签 1.配置模板 创建一个xlsx的模板文件&#xff0c;配置如下 该模板进行遍历了两次&#xff0c;因为我想要导出的数据分为两列展示&#xff0c;左右布局&#xff0c;一个循环实现不了&#xff0c;所以采…

计算机系列之面向对象、设计模式

24、面向对象技术&#xff08;重要&#xff0c;10分左右&#xff09; 1、面向对象开发 (1)对象:由数据及其操作所构成的封装体&#xff0c;是系统中用来描述客观事务的个实体&#xff0c;是构成系统的一个基本单位。一个对象通常可以由对象名、属性和方法3个部分组成。 (2)类…

YOLOV5更换转置卷积,助力涨点!

由于转置卷积是nn库自带的,所以我们直接找到models文件夹中的yolo.py文件中的 parse_model函数,再在如下图的地方添加转置卷积模块 # YOLOv5 🚀 by Ultralytics, AGPL-3.0 license """ YOLO-specific modules.Usage:$ python models/yolo.py --cfg yolov5s.…

ARM 交叉编译搭建SSH

一、源码下载 zlib&#xff1a;zlib-1.3.1.tar.xz openssl&#xff1a;openssl-0.9.8d.tar.gz openssh&#xff1a;openssh-4.6p1.tar.gz 二、交叉编译 1、zlib 编译参考这里 2、openssl tar -xf openssl-0.9.8d.tar.gz ./Configure --prefix/opt/ssh/openssl os/compile…

一对一WebRTC视频通话系列(五)——综合调试和功能完善

本系列博客主要记录一对一WebRTC视频通话实现过程中的一些重点&#xff0c;代码全部进行了注释&#xff0c;便于理解WebRTC整体实现。 本专栏知识点是通过<零声教育>的音视频流媒体高级开发课程进行系统学习&#xff0c;梳理总结后写下文章&#xff0c;对音视频相关内容感…

猿匹配,一款使用环信实现的一个开源聊天应用含服务器

前言 之前写了一篇Android开发集成聊天环信SDK3.x简单开始&#xff0c;然后最近得空开发了一款使用环信实现的实时聊天应用&#xff0c;包含简单的服务器端&#xff0c;并开源给大家&#xff0c;有兴趣的同学可以一起搞一下&#xff0c;详细介绍看下边吧 上代码 服务器&#…

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《计及全生命周期成本的公交光伏充电站储能优化配置方法》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

清华团队开发首个AI医院小镇模拟系统;阿里云发布通义千问 2.5:超越GPT-4能力;Mistral AI估值飙升至60亿美元

&#x1f989; AI新闻 &#x1f680; 清华团队开发首个AI医院小镇模拟系统 摘要&#xff1a;来自清华的研究团队最近开发出了一种创新的模拟系统&#xff0c;名为"Agent Hospital"&#xff0c;该系统能够完全模拟医患看病的全流程&#xff0c;其中包括分诊、挂号、…

【八十五】【算法分析与设计】单调栈的全新版本,两个循环维护左小于和右小于信息,84. 柱状图中最大的矩形,85. 最大矩形

84. 柱状图中最大的矩形 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 示例 1: 输入&#xff1a;heights [2,1,5,6,2,3] 输出&#xff1a;10 解释&am…

Go的安装与配置

安装 https://go.dev/dl/ 以Windows上安装为例&#xff1a; 下一步下一步&#xff0c;记住安装位置 安装完成后 win rcmd 键入go version检查是否安装成功 配置 Go 工作区 Go 在组织项目文件方面与其他编程语言不同。 Go 是在工作区的概念下工作的。但是从版本 1.11 开始&…

docker-compose部署java项目

docker-compose是定义和运行多容器的工具。换句话说就是通过配置yml文件来运行容器&#xff0c;简化了每次输入docker run等命令&#xff0c;把这些命令配置在yml文件统一管理&#xff0c;而且可以用一个yml文件一次启动多个容器&#xff0c;启动时还可以设置各个容器的依赖关系…

远程开机与远程唤醒BIOS设置

远程开机与远程唤醒BIOS设置 在现代计算机应用中&#xff0c;远程管理和控制已成为许多企业和个人的基本需求。其中&#xff0c;远程开机和远程唤醒是两项非常实用的功能。要实现这些功能&#xff0c;通常需要在计算机的BIOS中进行一些特定的设置。以下是对远程开机和远程唤醒…

如何判断nat网络?如何内网穿透

大家都清楚&#xff0c;如果你想开车&#xff0c;就必须要给车上一个牌照&#xff0c;随着车辆越来越多&#xff0c;为了缓解拥堵&#xff0c;就需要摇号&#xff0c;随着摇号的人数越来越多&#xff0c;车牌对于想开车的人来说已经成为奢望。在如今的IPv4时代&#xff0c;我们…

全自动减压器法二氧化碳气容量测试仪:饮料行业的革新与未来

全自动减压器法二氧化碳气容量测试仪&#xff1a;饮料行业的革新与未来 一、引言 在追求品质与效率的现代饮料生产领域&#xff0c;全自动减压器法二氧化碳气容量测试仪凭借其高精度、高效率及无人工干预的显著优势&#xff0c;正逐渐成为行业的标杆。特别是在碳酸饮料的生产中…

USB系列五:USB设备配置(重要)

在USB总线接口协议中&#xff0c;对于USB外部设备功能特征是通过端点&#xff08;Endpoint&#xff09;、配置&#xff08;Configuration&#xff09;和接口&#xff08;Interface&#xff09;来描述的&#xff0c;这些就是典型的USB描述符。 USB主机通过设备请求来读取外部设…

并行执行线程资源管理方式——《OceanBase 并行执行》系列 3

在某些特定场景下&#xff0c;由于需要等待线程资源&#xff0c;并行查询会遇到排队等待的情况。本篇博客将介绍如何管理并行执行线程资源&#xff0c;以解决这种问题。 《OceanBase并行执行》系列的内容分为七篇博客&#xff0c;本篇是其中的第三篇。前2篇如下&#xff1a; 一…

分布式与一致性协议之Quorum NWR算法

Quorum NWR算法 概述 不知道你在工作中有没有遇到过这样的事情:你开发实现了一套AP型分布式系统&#xff0c;实现了最终一致性&#xff0c;且业务接入后运行正常&#xff0c;一切看起来都那么美好。 可是突然有同事说&#xff0c;我们要拉这几个业务的数据做实时分析&#xf…

AXI4读时序在AXI Block RAM (BRAM) IP核中的应用

在本文中将展示描述了AXI从设备&#xff08;slave&#xff09;AXI BRAM Controller IP核与Xilinx AXI Interconnect之间的读时序关系。 1 Single Read 图1展示了一个从32位BRAM&#xff08;Block RAM&#xff09;进行AXI单次读取操作的时序示例。 图1 AXI 单次读时序图 在该…