当前位置：首页 > news >正文

【算法学习】最小公倍数问题

news 来源：原创 2025/8/7 23:57:08

前言：

求最小公倍数的两种算法：

求两个正整数的最小公倍数，比如3和5的最小公倍数是15，6和8的最小公倍数是24。

本片讨论如何求两个数的最小公倍数，第一种方法是通过最大公约数来求，第二种方法是累加法。

由最大公约数求最小公倍数

对于两个正整数a,b，这两个数的乘积等于这两个数的最小公倍数与最大公约数的乘积。

所以可以用该公式求最小公倍数。

计算两个正整数的最小公倍数(LCM)，可以通过最大公约数(GCD)和公式LCM(a,b)=(a*b)/GCD(a,b)实现。即LCM(a,b)=(a*b)/GCD(a,b)。所以只需求出最大公约数即可。

求最大公约数有两种算法：

1，辗转相除法（欧几里得算法）

其基本步骤如下：

用较大数除较小数，得到余数
用余数继续除上一次的除数，直到除数为0
最后的除数就是最大公约数

例如求91 和 49的最大公约数：

91/49=1......42

49/42=1......7

42/7=6......0

可以得到最大公约数为7。以除数和余数反复做除法运算，当余数为0时，取当前除数为最大公约数

代码实现：

自定义实现GCD函数

计算最大公约数
//int gcd(int a, int b)
//{
//	while (b != 0)
//	{
//		int tmp = b;
//		b = a % b;
//		a = tmp;
//	}
//	return a;
//}
int gcd(int a, int b)
{if (a % b == 0)return b;elsereturn gcd(b, a % b);
}
//计算最小公倍数
long long lcm(int a, int b)
{if(a==0||b==0)  return 0;return (a * b) / gcd(a, b);
}

使用C++17标准库中的std::gcd。

需包含头文件<numeric>，并使用C++17或更高标准编译。

#include <iostream>
#include <numeric>
using namespace std;long long lcm(int a, int b)
{return (a * b) / std::gcd(a, b);
}
int main()
{int a = 12, b = 18;cout << lcm(a, b) << endl;return 0;
}

总结：

公式推导
利用数学关系：LCM(a, b) × GCD(a, b) = |a × b|。

处理零的情况
如果任一数为零，直接返回 0（因为零和任何数的 LCM 是零）。

防止整数溢出
将 a * b 转换为 long long 类型，避免乘法溢出（例如 a = 1e9, b = 1e9）。

处理负数
使用 std::abs 保证计算的数值为正，避免符号干扰。

2，辗转相减法

若a>b,则a=a-b（大的数减去小的数）

若a=b,则a或b就是最大公约数

如求35和14的两个最小公倍数：

35-14=21；

21-14=7；此时7小于14，要做一次交换

14-7=7；

7-7=0；此时可以求出最大公约数位7

//a-b辗转相减法
int gcd(int a, int b)
{if (a < b){//交换int c = a;a = b;b = c;}if (a == b)return a;else{return gcd(b, a - b);}
}
long long lcm(int a, int b)
{if (a == 0 || b == 0) return 0;return (a * b) / gcd(a, b);
}

累加法

又称穷举法。设正数a。最后的最小公倍数一定是a,b的倍数。所以任选a,b一个作为循环变量，假设是a，若变量值除以b可以除尽，则此时的变量就是最小公倍数，否则变量依次+a。

long long lcm(int a, int b)
{int i = 0;for (int i = a;; i += a)if (i % b == 0)return i;
}

多个数的最小公倍数（扩展）

对于多个数的LCM，可以使用递归解决。

#include <iostream>
#include <vector>
using namespace std;
//辗转相除法
int gcd(int a, int b)
{if (a % b == 0)return b;elsereturn gcd(b, a % b);
}
//计算最小公倍数
long long lcm(int a, int b)
{return (a * b) / gcd(a, b);
}
long long lcm_mutiple(vector<int> num)
{if (num.size() == 0) return 0;long  long result = 1;for (int x : num)result = lcm(result, x);return result;
}
int main()
{cout << lcm_mutiple({ 2,5,9 }) << endl;return 0;
}

【算法学习】最小公倍数问题

前言： 求最小公倍数的两种算法： 求两个正整数的最小公倍数，比如3和5的最小公倍数是15，6和8的最小公倍数是24。本片讨论如何求两个数的最小公倍数，第一种方法是通过最大公约数来求，第二种方法是累加法。由…...

编程日记 2025/8/7 23:57:08

Spring Boot 整合 Apache Flink 教程

精心整理了最新的面试资料和简历模板，有需要的可以自行获取点击前往百度网盘获取点击前往夸克网盘获取 Spring Boot 整合 Apache Flink 教程一、背景与目标 Apache Flink 是一个高性能的分布式流处理框架，而Spring Boot提供了快速构建企业级应用的…...

编程日记 2025/8/7 23:56:19

进制转换（R转十）（1290. 二进制转换十进制、1292. 十六进制转十进制、1291. 八进制转十进制、1405. 小丽找潜在的素数）

题单地址：题单中心-东方博宜OJ 这里以二进制转十进制为例（按位加权求和法） 1290. 二进制转换十进制问题描述请将一个 25 位以内的 2 进制正整数转换为 1010 进制！ 输入一个 25 位以内的二进制正整数。输出该数对应的…...

编程日记 2025/8/7 23:55:00

通过启用Ranger插件的Hive审计日志同步到Doris做分析

以下是基于Apache Doris的Ranger Hive审计日志同步方案详细步骤，结合审计日志插件与数据导入策略实现： 一、Doris环境准备 1. 创建审计日志库表参考搜索结果的表结构设计，根据Ranger日志字段调整建表语句： CREATE DATABASE IF…...

编程日记 2025/8/7 23:56:17

Node.js框架Express、Koa、Koa2、Egg 和 NestJS 的对比分析

以下是 Express、Koa、Koa2、Egg 和 NestJS 的对比分析，从多个维度梳理它们的区别和适用场景： 1. 历史背景与定位框架背景与定位ExpressNode.js 早期框架，灵活轻量，生态丰富，适合快速开发简单应用。KoaExpress 原班团…...

编程日记 2025/8/7 13:44:11

蓝桥杯--冲刺题单--随时更新

冲刺题单感谢up主溶金落梧桐（uid:40733116），我是看了他的视频后总结的。简单模拟（循环数组日期进制） 1.蓝桥19723–分布式队列 package datasimulation;import java.util.Scanner;public class Test3 {//计算数组…...

编程日记 2025/8/7 23:44:06

新一代电子数据取证专家 | 苏州龙信信息科技有限公司

本文关键词：电子取证、手机取证、计算机取证、云取证关于我们About us 苏州龙信信息科技有限公司专注于电子数据取证、大数据、信息安全等领域，核心业务主要涵盖取证工具研发、大数据融合分析、案件技术支持、取证能力培训等，先后为执法部门…...

编程日记 2025/8/7 23:42:32

SSRF 攻击与防御：从原理到落地实践

1. 什么是 SSRF？ SSRF（Server-Side Request Forgery） 是一种常见的Web安全漏洞。当服务器提供了某种对外请求的功能，如“URL 参数直接转发请求”，攻击者就可以通过精心构造的URL，让服务器“自己”去访问特…...

编程日记 2025/8/7 23:46:53

socks 协议介绍

SOCKS协议详解一、基本定义与核心功能 SOCKS（Socket Secure）是一种网络传输协议，主要用于通过代理服务器转发客户端与目标服务器之间的通信请求。其核心功能包括隐藏用户真实IP地址、穿透防火墙限制以及支持多种网络协议（如TCP…...

编程日记 2025/8/7 15:14:56

不使用负压电源，ADC如何测量正负压？

电路图来自ZLinear的开源数据采集板卡DL8884_RFN，是一个比较常见的电压偏置采集法对电路进行分析，所以说可以先看下采集卡的模拟输入部分的参数如下： 通道数量: 8通道单端输入/4通道差分输入分辨率: 16位逐次逼近型(SAR) ADC 采样速率: 40…...

编程日记 2025/8/7 20:30:52

强推 Maven多镜像源快速切换工具，GUI操作超便捷

引言在开发过程中，配置Maven的settings.xml文件以优化依赖下载速度是一个常见的需求。然而，手动编辑XML文件不仅繁琐，还容易出错。本文将介绍如何使用Python和Tkinter构建一个图形界面工具，帮助开发者快速、安全地切换Maven镜像…...

编程日记 2025/8/2 16:33:51

Qt6.8实现麦克风音频输入音频采集保存wav文件

一.本文目的实现在Qt中接收麦克风数据并保存为WAV文件，使用QAudioInput来录音，并使用QFile来保存数据到WAV文件。开发环境：QT6.8 本文用极简代码实现，核心代码只需不到100行。二.代码实现...

编程日记 2025/6/30 20:16:26

自动驾驶AEB误触发率评估的必要测试里程估计

文章目录一问题背景与行业挑战二数学建模框架2.1 基础假设2.2 贝叶斯推断流程先验分布选择: 使用 Γ \Gamma Γ分布作为 λ \lambda λ的共轭先验参数 α 0 \alpha_0 α0和 β 0 \beta_0 β0的工程物理意义可靠性判断条件三数值求解方法1. 无信息先验场景 ( α 0 1 ,…...

编程日记 2025/8/7 8:27:43

python3 -m http.sever 8080加载不了解决办法

解决方法很多，本文设置各种处理方法，逻辑上需要根据你的自身情况选择我会告诉你遇到这种问题怎么做，根据具体症状处理如需转载，标记出处背景： 1。如图 2.。域名访问不了 http://www.meiduo.site:8080/register.html 上面的域名访问不了，下面的倒是正常 http://127…...

编程日记 2025/8/4 15:46:34

BYU-YOLO数据格式准备

BYU - Locating Bacterial Flagellar Motors 2025（在3D断层扫描图像中定位细菌鞭毛马达）一、数据介绍 1.竞赛介绍在本次竞赛中，您的任务是在3D断层扫描图像中找到鞭毛马达的中心位置。断层扫描图像是物体的三维体积表示。每个断层扫描图像作为一个独立的目录提供，其中…...

编程日记 2025/8/5 9:11:23

java NIO中的FileSystems工具类可以读取本地文件系统，ZIP/JAR等，无需解压处理，还可以复制文件

在Java NIO（java.nio.file包）中，FileSystems 是一个工具类，用于操作和管理文件系统。它提供了静态方法来获取或创建文件系统实例，并支持自定义文件系统实现。以下是其核心功能和用法： 1. 核心功能 (1) 获取…...

编程日记 2025/8/3 16:23:06

群体智能优化算法-模拟退火优化算法（Simulated Annealing, SA，含Matlab源代码）

摘要模拟退火（SA）算法是一种基于物理退火过程的全局优化算法，其核心思想来源于热力学中的退火过程：将材料加热到高温后再缓慢冷却，使其分子结构趋于最低能量状态，从而获得稳定结构。SA 算法利用 Metropol…...

编程日记 2025/8/3 1:37:14

knowledge-微前端(多个前端应用聚合的一个应用架构体系，每个小的应用可独立运行，独立开发，独立部署上线)

1.前言微前端，将一个大的前端应用拆分为多个小型的，独立开发的前端应用，每一个小型的应用都可以单独的开发，部署和运行。这种结构允许不同的团队使用不同的技术栈来开发应用的不同部分，提高开发的效率与灵活性。 2.实…...

编程日记 2025/8/5 18:55:16

目标检测中归一化的目的？

在目标检测任务中，归一化坐标和尺寸时需要除以图像的宽度和高度，主要有以下几个原因： 1. 统一尺度不同图像可能具有不同的宽度和高度。通过将坐标和尺寸除以图像的宽度和高度，可以将所有图像的标注信息统一到相同的尺度范围（[0, 1]）。这使得模型在训练和推理时能够处理…...

编程日记 2025/7/30 13:22:22

HarmonyOs- UIAbility应用上下文

上下文为何物上下文在计算机科学领域是一个广泛存在的概念。是现代操作系统核心抽象概念之一。其本质是环境信息的结构化封装。有过开发经验的都知道，当我们在一个系统上进行开发的时候，无论是Android，HarmonyOs，Linux 等等&a…...

编程日记 2025/8/7 18:59:57

鸿蒙开发真机调试：无线调试和USB调试

前言在鸿蒙开发的旅程中，真机调试堪称至关重要的环节，其意义不容小觑。虽说模拟器能够为我们提供初步的测试环境，方便我们在开发过程中快速预览应用的基本效果，但它与真机环境相比，仍存在诸多差异。就好比在模拟器中…...

编程日记 2025/8/2 18:53:27

【门店租金指定日期区间计算】

目录一、背景（一）业务场景（二）相关数据支撑二、计算方法统一封装（一）门店租金数据表格逻辑（二）业务逻辑详细解释（三）具体代码一、背景 （一&am…...

编程日记 2025/8/5 13:02:31

Dify：开源大模型应用开发平台全解析

从部署到实践，打造你的AI工作流一、项目简介 Dify 是一款面向开发者和企业的开源大语言模型（LLM）应用开发平台，旨在降低AI应用开发门槛，让用户通过可视化界面快速构建、管理和部署基于大模型的智能应用。其名称寓意“…...

编程日记 2025/8/5 4:37:58

使用DDR4控制器实现多通道数据读写（四）

在创建完DDR4的仿真模型后，我们为了实现异步时钟的读写，板卡中在PL端提供了一组差分时钟，可以用它通过vivado中的Clock Wizard IP核生成多个时钟，在这里生成两个输出时钟，分别作为用户的读写时钟，这样就可以…...

编程日记 2025/8/5 10:17:26

BFS--------N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode） 1.题目解析给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔&#xff08…...

编程日记 2025/8/5 7:48:44

蓝桥杯备考----小贪心+分类讨论问题---Popsicle

这道题有点小贪心的意思，小老鼠每次都想阻碍小猫最多，老鼠每次阻碍猫的话，可能是把0变成9 也可能是把1变成9，再有可能把2变成9，把3变成9，小老鼠的贪心就是尽可能更多的阻碍小猫拿冰棍，所以小老…...

编程日记 2025/8/6 16:18:56

强大的AI网站推荐（第一集）—— Devv AI

网站：Devv AI 号称：最懂程序员的新一代 AI 搜索引擎博主评价：我的大学所有的代码都是使用它，极大地提升了我的学习和开发效率。推荐指数：🌟🌟🌟🌟🌟&#x…...

编程日记 2025/8/7 11:48:18

现象 Tomcat 日志 org.springframework.web.servlet.handler.AbstractHandlerExceptionResolver.logException Resolved org.springframework.web.HttpMediaTypeNotAcceptableException: No acceptable representation HTTP状态 406 - 不可接收的报错，核心原因客…...

编程日记 2025/8/5 1:23:53

互联网it常用抓包工具说明

一、引言在互联网 IT 领域，无论是网络故障排查、安全检测，还是开发调试，抓包工具都发挥着举足轻重的作用。当网络出现故障，比如网页加载缓慢、应用无法连接服务器时，抓包工具可以帮助我们捕获网络数据包&#xff0…...

编程日记 2025/8/2 16:51:06

RS485总线加终端电阻可能存在的问题

目录 1、降低驱动信号幅值 2、增大通信线压降 3、增大收发器功耗 4、降低总线空闲时的差分电压尽管终端电阻能有效减少信号反射、提高信号质量，但它也引入了一系列问题，需要在设计中谨慎考虑。以下是几个常见问题的详细分析： 1、降低驱…...

编程日记 2025/8/5 14:20:27

在 Linux 系统上部署 Deepseek AI 的全面指南‌

对于所有希望亲身体验 AI 魅力的玩家来说，本文将提供一个详尽的教程，指导你在 Linux 系统上部署 Deepseek AI。无论你是技术小白还是有一定基础的用户，都能轻松跟随本文完成部署。 ‌一、关于 Ollama‌ Ollama 是一款功能强大的开源应用&am…...

编程日记 2025/8/4 19:09:05

Docker下载，包含Win、Mac

介绍 Docker 是一种开源的容器化平台，通过操作系统级虚拟化技术实现应用的快速开发、部署和运行。以下从多个维度对 Docker 进行详细介绍： 一、Docker 的核心概念与功能容器化技术 Docker 利用 Linux 内核的容器隔离技术（如 Cgroups 和 Nam…...

编程日记 2025/8/4 19:35:37

算法｜2025最强优化算法

根据2025年的最新研究进展，以下是被广泛认可的几种“最强优化算法”，它们在理论创新、性能表现和应用范围上均有显著突破： 一、植物根茎生长优化算法（PRGO） 1 - 核心原理：灵感来源于植物根系结构&#xf…...

编程日记 2025/8/5 19:44:23

Prime: 1靶场渗透测试

Prime: 1 来自 <Prime: 1 ~ VulnHub> 1，将两台虚拟机网络连接都改为NAT模式 2，攻击机上做namp局域网扫描发现靶机 nmap -sn 192.168.23.0/24 那么攻击机IP为192.168.23.182，靶场IP192.168.23.207 3，对靶机进行端口服务探测…...

编程日记 2025/8/3 10:39:21

html相关常用语法

html相关常用语法 HTML（HyperText Markup Language）即超文本标记语言，是用于创建网页的标准标记语言 HTML使用标记语言描述Web页面的结构 HTML元素是HTML页面的建构快 HTML元素通过标签tag来表示 HTML标签是“标题”、”段落“、”表格“等内…...

编程日记 2025/8/5 0:00:27

2025年R1 快开门式压力容器操作证考试题目及答案解析

R1 快开门式压力容器操作证考试题目及答案： 单选题 1、快开门式压力容器的快开门（盖）应设计安全联锁装置并应具有（ ）功能。 A. 当快开门达到预定关闭部位方能升压运行的安全联锁功能 B. 当压力容器的内部压力完全释…...

编程日记 2025/8/4 19:01:03

《傲慢与偏见》（Pride and Prejudice）简介

学习《傲慢与偏见》本文缘于阅读床头灯3000词英文版《傲慢与偏见》。读完之后，想要了解的更深一点。英语学习记录：床头灯3000词：《傲慢与偏见》（Pride and Prejudice）阅读记录故事梗概《傲慢与偏见》&#xff08…...

编程日记 2025/8/6 19:14:08

绿盟科技春招面试

《网安面试指南》https://mp.weixin.qq.com/s/RIVYDmxI9g_TgGrpbdDKtA?token1860256701&langzh_CN 5000篇网安资料库https://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247486065&idx2&snb30ade8200e842743339d428f414475e&chksmc0e4732df793fa3bf39…...

编程日记 2025/8/1 5:44:06

dpkg-architecture命令详解

dpkg-architecture 是 Debian 系系统中用于处理软件包架构相关操作的工具，尤其在软件包构建和交叉编译环境中至关重要。以下是其核心功能及用法的详细说明： ‌一、核心功能‌ ‌架构查询与验证‌ 显示或验证当前系统（DEB_HOST_ARCH&#xff…...

编程日记 2025/8/6 21:06:33

阿里的MNN源码如何编译成so文件，供Android调用

在Ubtuntu下面的编译，先整理编译环境 1、安装环境依赖 # 安装必要工具 sudo apt update sudo apt install -y cmake ninja-build git wget # 安装Android NDK（建议使用r21版本或更高） wget https://dl.google.com/android/repository/a…...

编程日记 2025/8/7 9:14:26

【高项】信息系统项目管理师（九）项目资源管理【4分】

项目资源管理包括识别、获取和管理所需资源以成功完成项目的各个过程，这些过程有助于确保项目经理和项目团队在正确的时间和地点使用正确的资源。项目资源是指对于项目来说，一切具有使用价值，可为项目接受和利用，且属于项目发展过程所需的客观存在的资源，包括实物资源和团…...

编程日记 2025/8/3 5:06:55

hive 数据简介

Hive介绍 1）Hive简介 Hive是基于Hadoop的一个数据仓库工具，用于结构化数据的查询、分析和汇总。Hive提供类SQL查询功能，它将SQL转换为MapReduce程序。 Hive不支持OLTP，Hive无法提供实时查询。 2）Hive在大数据生态环境…...

编程日记 2025/8/5 19:42:17

SpringBoot的启动原理？

大家好，我是锋哥。今天分享关于【SpringBoot的启动原理？】面试题。希望对大家有帮助； SpringBoot的启动原理？ 1000道互联网大厂Java工程师精选面试题-Java资源分享网 Spring Boot的启动原理主要是通过 SpringApplication 类来…...

编程日记 2025/8/6 6:55:49

蓝桥杯2023年第十四届省赛真题-子矩阵

题目来自DOTCPP： 暴力思路（两个测试点超时）： 题目要求我们求出子矩阵的最大值和最小值的乘积，我们可以枚举矩阵中的所有点，以这个点为其子矩阵的左上顶点，然后判断一下能不能构成子矩阵。如果可…...

编程日记 2025/8/6 8:16:27

hackmyvm-connection

connection(利用445端口smb) ubuntu:192.168.89.225(这里使用ubuntu代替centos7) connection:192.168.89.47 kali:192.168.89.149 arp-scan -l nmap -sS -v 192.168.36.47 nmap 192.168.89.47 --script vuln 使用nmap vuln扫描192.168.111.80靶机，观察可能存在的…...

编程日记 2025/8/4 10:40:36