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

深入解析最大公约数（GCD）与最小公倍数（LCM）的C++实现

news 来源：原创 2025/7/5 18:08:42

深入解析最大公约数（GCD）与最小公倍数（LCM）的C++实现

一、GCD与LCM的数学定义

1. 最大公约数（GCD）

两个或多个整数共有约数中最大的一个。
例如：

GCD(12, 18) = 6
GCD(21, 14) = 7

2. 最小公倍数（LCM）

两个或多个整数的最小公倍数。
例如：

LCM(4, 6) = 12
LCM(8, 12) = 24

数学关系：
[
\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}
]

二、欧几里得算法：GCD的高效实现

1. 递归实现（数学原理）

#include <iostream>
using namespace std;int gcd_recursive(int a, int b) {a = abs(a); // 处理负数b = abs(b);return b == 0 ? a : gcd_recursive(b, a % b);
}

2. 非递归实现（性能优化）

int gcd_iterative(int a, int b) {a = abs(a);b = abs(b);while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}

3. 边界条件处理

输入为0：GCD(0, a) = |a|
两数均为0：数学上未定义，代码返回0

// 示例测试
cout << gcd_recursive(0, 5) << endl;    // 输出5
cout << gcd_iterative(0, 0) << endl;    // 输出0

三、LCM的实现与溢出处理

1. 基础实现

int lcm(int a, int b) {a = abs(a);b = abs(b);if (a == 0 || b == 0) return 0; // 处理0值int gcd_val = gcd_iterative(a, b);return (a / gcd_val) * b; // 防止溢出
}

2. 大数优化（使用long long）

long long lcm_safe(long long a, long long b) {a = abs(a);b = abs(b);if (a == 0 || b == 0) return 0;long long gcd_val = gcd_iterative(a, b);return (a / gcd_val) * b; // 先除后乘
}

3. 测试验证

cout << lcm(12, 18) << endl;        // 输出36
cout << lcm_safe(123456789, 987654321) << endl; // 输出121932631112635269

四、性能对比与算法分析

实现方式	时间复杂度	适用场景	优点
递归GCD	O(log n)	代码简洁	易理解，适合教学
非递归GCD	O(log n)	高并发场景	无栈溢出风险，性能稳定
基础LCM	O(log n)	常规计算	依赖GCD实现，逻辑清晰
大数安全LCM	O(log n)	大数值处理	避免中间结果溢出

五、实际应用场景

1. 分数运算简化

// 分数加法：a/b + c/d
int numerator = a*d + b*c;
int denominator = b*d;
int gcd_val = gcd(numerator, denominator);
cout << numerator/gcd_val << "/" << denominator/gcd_val;

2. 周期性事件调度

// 两事件周期为t1和t2，求共同发生周期
int t1 = 15, t2 = 20;
cout << "共同周期：" << lcm(t1, t2); // 输出60

3. 密码学与模运算

// RSA算法中计算φ(n)
int p = 61, q = 53;
int phi = lcm(p-1, q-1); // φ(n) = LCM(p-1, q-1)

六、C++标准库支持

C++17引入的`<numeric>`函数

#include <numeric>
cout << gcd(12, 18) << endl;    // 输出6
cout << lcm(12, 18) << endl;    // 输出36

七、常见问题与解决方案

负数输入：在计算前取绝对值
零值处理：LCM(0, a) = 0，GCD(0, 0)需特殊处理
整数溢出：使用更大数据类型或调整运算顺序
递归深度：非递归实现避免栈溢出

掌握GCD与LCM的高效实现，不仅是算法基础，更是解决实际工程问题的关键。通过本文的代码实现与原理分析，开发者可以深入理解其数学本质，并在数值计算、密码学、调度系统等领域灵活应用。

深入解析最大公约数（GCD）与最小公倍数（LCM）的C++实现

深入解析最大公约数（GCD）与最小公倍数（LCM）的C实现一、GCD与LCM的数学定义 1. 最大公约数（GCD） 两个或多个整数共有约数中最大的一个。例如： GCD(12, 18) 6GCD(21, 14) 7 2. 最小公倍数…...

编程日记 2025/7/5 18:08:42

低功耗LPWAN模块开发指南：远距离无线通信与边缘计算融合实战‌

在远程资产追踪、野外环境监测等场景中，稳定可靠的长距离通信与超低功耗是系统设计的核心挑战。eFish-SBC-RK3576通过 ‌原生双UART接口 USB OTG扩展能力‌ ，可无缝集成主流LPWAN模组（LoRa/NB-IoT），实现“数据采集-边…...

编程日记 2025/7/5 17:52:47

【质量管理】纠正、纠正措施和预防的区别与解决问题的四重境界

“质量的定义就是符合要求”，我们在文章【质量管理】人们对于质量的五个错误观念-CSDN博客中提到过，这也是质量大师克劳士比所说的。“质量的系统就是预防”，防止出现产品不良而造成的质量损失。质量问题的解决可以从微观和宏观两个方面来考…...

编程日记 2025/7/5 17:10:23

STM32F103_LL库+寄存器学习笔记12 - 提高串口通讯程序的健壮性：异常监控 + 超时保护机制

导言首先，进行USART和DMA状态监测、记录异常状态并主动处理，是高健壮性嵌入式系统开发的核心思想之一。这种机制看似复杂，实则能有效保障系统长期、稳定地运行： 提升通讯可靠性。降低维护成本。增强系统自恢复能力。因此&…...

编程日记 2025/7/5 17:52:47

搜索-BFS

马上蓝桥杯了，最近刷了广搜，感觉挺有意思的，广搜题类型都差不多，模板也一样，大家写的时候可以直接套模板这里给大家讲一个比较经典的广搜题-迷宫题目问问能否走到 (n,m) 位置，假设最后一个点是我们的&…...

编程日记 2025/7/5 16:52:20

Keil调试(RTT Debug 断点)

调试打印操作方式接口优缺点串口打印TXRX简单,但是占用串口,速度慢,重定向fputc简单RTT打印SWDIOSWCLK速度快,不占额外接口,直接移植RTT库断点打印SWDIOSWCLKDebug的时候断点操作SWOSWDIOSWCLKSWO需要连接SWO引脚,重定向fputc简单这里我只介绍RTT打印和断点打印; 一. RT…...

编程日记 2025/7/5 17:06:22

【jQuery】插件

目录一、 jQuery插件 1. 瀑布流插件： jQuery 之家 http://www.htmleaf.com/ 2. 图片懒加载： jQuery 插件库 http://www.jq22.com/ 3. 全屏滚动总结不易~ 本章节对我有很大收获，希望对你也是~~~ 一、 jQuery插件 jQuery 功能…...

编程日记 2025/6/30 9:57:35

leetcode 28 Find the Index of the First Occurrence in a String

直接用kmp算法 class Solution { public:int strStr(string haystack, string needle) {return kmp(haystack,needle);}int kmp(std::string &text,std::string &pattern){int n text.size();int m pattern.size();if(m 0)return 0;std::vector<int> next;ne…...

编程日记 2025/7/5 17:08:42

nginx 动静分离

一.动静分离 1.动静分离的好处 Apache Tocmat 严格来说是一款java EE服务器，主要是用来处理 servlet请求。处理css、js、图片这些静态文件的IO性能不够好，因此，将静态文件交给nginx处理，可以提高系统的访问速度，减少…...

编程日记 2025/7/5 18:04:26

1.2 斐波那契数列模型：LeetCode 面试题 08.01. 三步问题

动态规划解三步问题：LeetCode 面试题 08.01. 三步问题 1. 题目链接 LeetCode 面试题 08.01. 三步问题题目要求：小孩上楼梯，每次可以走1、2或3步，计算到达第 n 阶台阶的不同方式数，结果需对 1e9 7 取模。 2. 题目描述…...

编程日记 2025/7/5 17:15:41

关于AutoMapper

AutoMapper 概述 AutoMapper 是一个基于约定的对象 - 对象映射库，主要用于在不同对象类型之间自动映射属性值。它能根据配置的映射规则，将源对象的属性值填充到目标对象中，避免了手动编写大量繁琐的对象映射代码。作用提升开发效率&…...

编程日记 2025/7/5 16:45:19

是否每一层之间都要线性变换和激活函数？

1. 神经网络层的基本组成一个典型的神经网络层通常包含两个步骤： 线性变换（加权求和）： z Wx} b 其中W 是权重矩阵，b是偏置向量，是输入，z 是线性输出。激活函数： 其中&#xff0c…...

编程日记 2025/7/5 17:39:49

golang 的reflect包的常用方法

目录 reflect 包方法总结类型 (Type) 方法值 (Value) 方法代码示例： reflect 包方法总结 p : Person{Name: "小明", Age: 22}t : reflect.TypeOf(&p)v : reflect.ValueOf(p) 类型 (Type) 方法方法名描述示例　　　　　　　　　　　　　　　Na…...

编程日记 2025/7/5 17:37:10

CentOS 7 安装 EMQX (MQTT)

CentOS 7 安装 EMQX 通过 Yum 源安装 EMQX 支持通过 Yum 源安装，您可通过以下 Yum 命令从中自动下载和安装 EMQX。通过以下命令配置 EMQX Yum 源： curl -s https://assets.emqx.com/scripts/install-emqx-rpm.sh | sudo bash安装以下依赖项&#xff…...

编程日记 2025/7/5 17:34:13

Flask项目部署:Flask + uWSGI + Nginx

目录 1,网络架构 2,环境安装 2.1,安装yum:Shell软件包管理器 2.2 安装python 2.3 安装uWSGI 2.4 安装Flask 3,上传工程包到服务器,打包Flask项目 4,创建和配置 uwsgi 配置文件 uwsgi.ini 4.1配置文件 4.2配置文件注释详解 5,启动服务 6,安装nginx 7,nginx配置 8,…...

编程日记 2025/7/5 17:07:02

软件工程面试题（十五）

1、servlet 创建过程以及ruquest，response，session的生命周期？ Servlet的创建过程：第一步 public class AAA extends HttpServlet{ 实现对应的doxxx方法 } 第二步: 在web.xml中配置 <servlet> <servlet-name></servlet-name> <servlet-c…...

编程日记 2025/7/5 18:05:12

当Kafka化身抽水马桶：论组件并发提升与系统可用性的量子纠缠关系

《当Kafka化身抽水马桶：论组件并发提升与系统可用性的量子纠缠关系》引言：一场OOM引发的血案某个月黑风高的夜晚，监控系统突然发出刺耳的警报——我们的数据发现流水线集体扑街。事后复盘发现：Kafka集群、Gateway、Discovery服…...

编程日记 2025/7/5 17:55:17

python和Java的区别

Python和Java是两种流行的编程语言，它们之间有一些重要的区别： 语法：Python是一种动态类型的脚本语言，语法简洁明了，通常使用缩进来表示代码块。Java是一种静态类型的编程语言，语法更为严格，需要…...

编程日记 2025/7/5 18:02:55

QFlightInstruments飞行仪表控件库

QFlightInstruments 是一个开源的飞行仪表控件库，专为基于 Qt 的应用程序设计。它提供了一系列仿真实飞机仪表的组件，适用于飞行模拟软件、航空电子系统或任何需要高仿真飞行仪表显示的项目。主要功能高仿真飞行仪表：包括空速表、高度表、…...

编程日记 2025/7/5 18:07:50

可发1区的超级创新思路（python\matlab实现）：MPTS+Lconv+注意力集成机制的Transformer时间序列模型

首先声明，该模型为原创！原创！原创！且该思路还未有成果发表，感兴趣的小伙伴可以借鉴！应用场景该模型主要用于时间序列数据预测问题，包含功率预测、电池寿命预测、电机故障检测等等。一、模型整体架构（本文以光伏功率预测为例）本模型由多尺度特征提取模块（MPTS）…...

编程日记 2025/6/28 7:08:56

Nginx — Nginx版本升级

例如：将10.224.11.220、10.224.11.221、10.208.11.220 三台服务器上的Nginx从1.21.1版本升级到1.23.3版本。一、Nginx升级步骤步骤一：备份老版本的Nginx（10.224.11.220、10.224.11.221、10.208.11.220） #关闭Nginx cd /usr/l…...

编程日记 2025/7/3 19:44:39

CSS学习笔记6——网页布局

目录一、元素的浮动属性、清除浮动清除浮动的其他方法 1、使用空标签清除浮动影响 2、使用overflow属性清除浮动 3、使用伪元素清除浮动影响原理 overflow属性二、元素的定位 1、相对定位 2、绝对定位编辑 3、固定定位 z-index层叠等级属性一、元素的浮动…...

编程日记 2025/7/5 17:38:43

C语言【指针二】

引言介绍：const修饰指针，野指针应用：指针的使用（strlen的模拟实现），传值调用和传指调用一、const修饰指针 1.const修饰变量简单回顾一下前面学过的const修饰变量：在变量前面加上const&…...

编程日记 2025/6/28 4:06:54

第十六届蓝桥杯模拟二（串口通信）

由硬件框图可以知道我们要配置LED 和按键一.LED 先配置LED的八个引脚为GPIO_OutPut，锁存器PD2也是，然后都设置为起始高电平，生成代码时还要去解决引脚冲突问题二.按键按键配置，由原理图按键所对引脚要GPIO_Input 生成代码，在文件夹中添加code文件夹，code中添加fun.…...

编程日记 2025/6/30 20:20:10

Java List 集合取交集、并集、差集、补集

在Java中，集合操作是编程中非常常见的需求，尤其是在处理数据集合时，如List、Set等。本文将详细介绍如何在Java中实现List集合的交集、并集、差集和补集操作，并提供代码示例和实现方法。 1. 交集操作交集是指两个集合中都存在的元…...

编程日记 2025/6/27 11:24:53

SkyWalking+Springboot实战

1、下载SkyWalking APM 1.手动下载 Downloads | Apache SkyWalkinghttps://skywalking.apache.org/downloads/ 2.链接下载 https://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-apm-10.2.0.tar.gzhttps://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-…...

编程日记 2025/7/5 4:37:25

【小兔鲜】day01 项目、Vue3介绍、组合式API、小案例

【小兔鲜】day01 项目、Vue3介绍、组合式API、小案例 0. 市场上Vue前端工程师用到的技术1. Vue3小兔鲜先导课1.1 技术栈1.2 项目规模1.3 项目亮点1.4 课程安排 2. 认识Vue32.1 Vue3组合式API体验 3. create-vue创建Vue3项目3.1 新建项目结构3.2 小节3.3 补充说明npm init vuela…...

编程日记 2025/7/4 14:17:52

【Pandas DataFrame】

以下是 Pandas DataFrame 的核心知识点总结，用结构化分类帮你高效记忆关键操作和概念： 1. 基础操作创建DataFrame 方法代码示例说明从字典创建df pd.DataFrame({A: [1,2], B: [3,4]})字典键为列名，值为数据从列表创建df pd.DataFrame([[…...

编程日记 2025/7/4 11:42:44

华为OD机试2025A卷 - 生成回文素数（Java Python JS C++ C ）

最新华为OD机试真题目录：点击查看目录华为OD面试真题精选：点击立即查看题目描述求出大于或等于 N 的最小回文素数。如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。例如，2，3，5，7，11 以及 13 是素数。如果一个数从左往右读与从右往左读是一…...

编程日记 2025/6/27 15:30:42

Jenkins教程(自动化部署)

Jenkins教程(自动化部署) 1. Jenkins是什么？ Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具，广泛用于项目开发，具有自动化构建、测试和部署等功能。Jenkins用Java语言编写，可在Tomcat等流行的servlet容器中运行&…...

编程日记 2025/7/3 5:14:55

C#里使用libxl的对齐/边框/颜色

一份好的EXCEL文件，通道会有不同的颜色和边框来表示。以便表示一些重要的信息，这样才能让人们一眼就看到需要关注的信息。如下面所示：要显示上面的内容，需要使用下面的例子： private void button12_Click(object sender, EventArgs e){var book = new ExcelBook();if…...

编程日记 2025/7/3 4:39:28

虚拟pinctrl驱动

之前呢，我们讲解了在内核中pinctrl子系统是怎么实现的，今天我们来尝试一下自己去写一个pinctrl子系统： 首先呢，我们来看看一个pinctrl子系统需要做的事情: 上面的话，我们看了一个pinctrl子系统需要的三大功能以及在驱…...

编程日记 2025/6/28 4:23:29

pycharm虚拟环境项目转移后配置解释器

添加解析器提示：无效的 Python SDK 解决方法在到电脑安装python解析器，复制：python.exe和pythonw.exe 项目虚拟环境venv/Scripts Python解释器添加项目现有虚拟环境，就可以正常使用...

编程日记 2025/6/28 3:50:27

蓝桥杯嵌入式学习笔记

用博客来记录一下参加蓝桥杯嵌入式第十六届省赛的学习经历工具环境准备cubemx配置外部高速时钟使能设置串口时钟配置项目配置 keil配置烧录方式注意代码规范头文件配置模块ledcubemx配置keil代码实现点亮一只灯实现具体操作的灯，以及点亮还是熄灭按键cubemx配置k…...

编程日记 2025/7/3 11:49:22

0201-jsx语法基础-jsx-仿低代码平台项目

文章目录 1.jsx标签2.jsx属性3.jsx 事件3.1 声明事件3.2 使用事件（对象） 4. typescript类型基础4.1 类型声明4.2 事件函数传递自定义参数 5.插入js变量6. 条件判断7. 循环结语 1.jsx标签 jsx标签与html标签区别： 首字母大小写大写是自定义组…...

编程日记 2025/6/30 17:07:18

在MCU工程中优化CPU工作效率的几种方法

在嵌入式系统开发中，优化 CPU 工作效率对于提升系统性能、降低功耗、提高实时性至关重要。Keil 作为主流的嵌入式开发工具，提供了多种优化策略，包括关键字使用、内存管理、字节对齐、算法优化等。本文将从多个方面介绍如何在 Keil 工程中优…...

编程日记 2025/7/3 1:22:43

Elasticsearch 的搜索功能

Elasticsearch 的搜索功能建议阅读顺序： Elasticsearch 入门Elasticsearch 搜索（本文）Elasticsearch 搜索高级Elasticsearch 高级 1. 介绍使用 Elasticsearch 最终目的是为了实现搜索功能，现在先将文档添加到索引中&#xff0c…...

编程日记 2025/7/2 18:22:48

【鸿蒙5.0】向用户申请麦克风授权

#效果图步骤在 config.json 里声明权限：在项目的 config.json 文件中添加麦克风权限的声明，告知系统应用需要使用该权限。检查权限状态：在代码里检查应用是否已经获得了麦克风权限。请求权限：若应用未获得麦克风权限&#xff0…...

编程日记 2025/7/1 1:18:51

数据结构与算法分析：树与哈希表（一）

遇到的问题，都有解决方案，希望我的博客能为你提供一点帮助。一、概述背景：链表处理大量数据时，线性访问耗时多。二叉查找树多数操作平均运行时间为 O (log N)，相对于链表树更加高效。 1.预备知识 1.1. 树的定义与…...

编程日记 2025/7/4 17:40:09

VBA第三十四期 VBA中怎么用OnKey事件

我们在VBA设计中经常需要使用到OnKey方法，特别是在窗口设计中比如我们想用到翻页按键，则就可以来建立一个OnKey事件。Setup_OnKey过程运行以后，就会达到最终效果，按PgDn键会将指针下移一行，按PgUp键会将指针上移一行。…...

编程日记 2025/7/2 23:14:56

HarmonyOS NEXT开发进阶（十五）：日志打印 hilog 与 console.log 的区别

文章目录一、前言二、两者区别对比三、HiLog 详解四、拓展阅读一、前言在日常开发阶段，日志打印是调试程序非常常用的操作，在鸿蒙的官方文档中介绍了hilog这种方式，前端转过来的开发者发现console.log也可以进行日志打印，而且…...

编程日记 2025/7/4 10:25:00

Skynet 框架中 gateserver、gate、watchdog 的关系

一、概述在 Skynet 框架的网络通信架构中，gateserver、gate、watchdog 是三个核心组件，共同实现客户端连接的监听、管理和业务逻辑的分发。其设计目标是通过分层解耦，提升网络层的稳定性与业务逻辑的灵活性。二、组件职责 1. ‌gateserve…...

编程日记 2025/6/28 1:27:46

第11章:优化I/O_《C++性能优化指南》_notes

第十一章核心知识点详解 11.1 读取文件的优化技巧重点：减少内存分配、使用大缓冲区、优化函数调用链。难点：理解系统调用开销与缓冲区大小的权衡。代码示例与详解示例1：使用高效函数签名和减少内存分配 #include <fstream> #inc…...

编程日记 2025/6/27 5:58:12

【C++初阶】--- 内存管理

1.C/C内存分布我们一般说的32位机器和64位机器指的是虚拟空间的大小，也就是进程地址空间的大小，32位机器下，进程地址空间的大小是232个字节，也就是4G，64位机器下，进程地址空间的大小是264个字节,大概160亿…...

编程日记 2025/7/2 1:21:11

使用 Ansys Discovery 可视化液体池中的水流

了解 ANSYS Discovery：设计领域的变革者 ANSYS Discovery 是一款功能强大的软件工具，能够彻底改变设计流程。借助其先进的仿真功能，工程师现在可以在设计投入生产之前更深入地了解其设计。通过使用 ANSYS Discovery，设计师可以快…...

编程日记 2025/7/2 4:22:19

网络安全-网络安全基础

一、网络安全概述 TCP/IP协议定义了一个对等的开放性网络，使得连接到这个网络中的所有用户都可能面临来自网络中的恶意的破坏和攻击。这些攻击通过网络通信协议、网络应用协议甚至物理传输链路来实现。主要针对于软件和硬件进行攻击。那在互联网上如何保证自己的安…...

编程日记 2025/6/30 5:00:27

YOLOv8+ Deepsort+Pyqt5车速检测系统

该系统通过YOLOv8进行高效的目标检测与分割，结合DeepSORT算法完成目标的实时跟踪，并利用GPU加速技术提升处理速度。系统支持模块化设计，可导入其他权重文件以适应不同场景需求，同时提供自定义配置选项，如显示标签和保存…...

编程日记 2025/7/3 7:54:56

QML中的附加属性和附加信号处理程序

QML中的附加属性和附加信号处理程序在QML中，附加属性(Attached Properties)和附加信号处理程序(Attached Signal Handlers)是特殊类型的属性和信号，它们由附加类型(Attached Types)提供，而不是由对象本身直接提供。什么是附加的(Attached…...

编程日记 2025/6/28 3:08:31

爱普生FC-135晶振5G手机的极端温度性能守护者

在5G时代，智能手机不仅需要高速率与低延迟，更需在严寒、酷暑、振动等复杂环境中保持稳定运行。作为 5G 手机的核心时钟源，爱普生32.768kHz晶振FC-135凭借其宽温适应性、高精度稳定性与微型化设计，成为5G手机核心时钟源的理想选择&…...

编程日记 2025/7/2 4:00:14

GPT Workspace体验

GPT Workspace是一款将强大的自然语言处理模型（如 ChatGPT 和 Gemini）集成到 Google Workspace 应用（如 Google Docs, Sheets, Slides, Gmail 和 Drive）中的工具或插件。它的目标是提升用户在日常办公中的效率和创造力。以下是对…...

编程日记 2025/7/3 13:20:58

深入解析最大公约数（GCD）与最小公倍数（LCM）的C++实现

一、GCD与LCM的数学定义

1. 最大公约数（GCD）

2. 最小公倍数（LCM）

二、欧几里得算法：GCD的高效实现

1. 递归实现（数学原理）

2. 非递归实现（性能优化）

3. 边界条件处理

三、LCM的实现与溢出处理

1. 基础实现

2. 大数优化（使用long long）

3. 测试验证

四、性能对比与算法分析

五、实际应用场景

1. 分数运算简化

2. 周期性事件调度

3. 密码学与模运算

六、C++标准库支持

C++17引入的<numeric>函数

七、常见问题与解决方案

相关文章：

C++17引入的`<numeric>`函数