研究整除的性质——最大公约数（GCD）和最小公倍数（LCM）

devtools/2025/3/15 10:29:37/

        最大公约数（GCD）和最小公倍数（Least Common Multiple，LCM）研究整除的性质，非常古老，在2000多年前就得到了很好的研究。由于简单易懂，有较广泛的应用，它们是竞赛中频繁出现的考点。

一、最大公约数（GCD）

1、GCD 的定义

        最大公约数（Greatest Common Divisor，GCD）指两个或多个整数共有约数中最大的一个。例如，12 和 18 的公约数是 1、2、3、6，其中最大的是 6，因此 gcd(12, 18) = 6。

2、GCD的符号

        整数a和b的最大公约数是能同时整除a和b的最大整数，记为gcd(a,b)。负整数也可以算GCD，不过由于-a的因子和a的因子相同，在编码时只需要关注正整数的最大公约数。下面用C++函数std::_gcd(a,b)演示GCD的计算结果，GCD 的结果的符号通常与第一个参数的符号相同。

# include <bits/stdc++.h>
// 包含C++标准库的头文件，通常用于竞赛编程，包含了几乎所有常用的库。using namespace std;
// 使用标准命名空间，避免每次调用标准库函数时都要加std::前缀。int main(){// 主函数，程序的入口。cout << __gcd(45,9) << "\n"; //9// 计算45和9的最大公约数，输出9。cout << __gcd(0,42) << "\n"; //42// 计算0和42的最大公约数，输出42。cout << __gcd(42,0) << "\n"; //42// 计算42和0的最大公约数，输出42。cout << __gcd(0,0) << "\n"; //0// 计算0和0的最大公约数，输出0。cout << __gcd(20,15) << "\n"; //5// 计算20和15的最大公约数，输出5。cout << __gcd(-20,15) << "\n"; //-5// 计算-20和15的最大公约数，输出-5。cout << __gcd(20,-15) << "\n"; //5// 计算20和-15的最大公约数，输出5。cout << __gcd(-20,-15) << "\n"; //-5// 计算-20和-15的最大公约数，输出-5。cout << __gcd((long long)98938441343232,(long long)33422) << "\n"; //2// 计算98938441343232和33422的最大公约数，输出2。
}

3、GCD 的性质

  1. 交换律：gcd(a, b) = gcd(b, a)

  2. 结合律：gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)

  3. 线性组合：gcd(a, b) 能整除任何形如 ax + by 的线性组合（x, y 为整数）

  4. 与倍数的关系：

    • 若 a 整除 b，则 gcd(a, b) = |a|

    • gcd(ka, kb) = |k|·gcd(a, b)（k 为整数）

  5. 贝祖定理：存在整数 x 和 y，使得 ax + by = gcd(a, b)

  6. 余数性质：gcd(a, b) = gcd(b, a mod b)（欧几里得算法核心）

  7. 几个性质：(1) gcd(a,b)=gcd(a,a+b)=gcd(a,k·a+b)。
    (2) gcd(ka,kb)=k·gcd(a,b)。
    (3) 多个整数的最大公约数：gcd(a,b,c)=gcd(gcd(a,b),c)。
    (4) 若gcd(a,b)=d，则gcd(a/d,b/d)=1，即a/d与b/d互素。这个定理很重要。
    (5) gcd(a+cb,b)=gcd(a,b)。

3、欧几里得算法（辗转相除法）

算法思想

        基于性质 6，反复用较大数除以较小数，用余数替换较大数，直到余数为 0。最后一个非零余数即为 GCD。

步骤：

  1. 若 b = 0，返回 a

  2. 否则，计算 a mod b，递归求解 gcd(b, a mod b)

数学证明：
        若 d = gcd(a, b)，则 d 能整除 a 和 b，因此也能整除 a mod b = a - qb（q 为商）。同理，d 也是 b 和 a mod b 的公约数，故两数对的公约数集合相同，最大公约数相等。

时间复杂度

  • 最优：O(1)（当其中一个数为 0 时）

  • 最坏：O(log min(a, b))（每次取模至少减少一半）

5、C++ 实现

1. 递归实现

#include <iostream>
#include <cstdlib> // 用于 abs 函数int gcd(int a, int b) {if (b == 0)return abs(a); // 处理负数情况return gcd(b, a % b);
}int main() {std::cout << gcd(48, 18) << std::endl;  // 输出 6std::cout << gcd(-12, 15) << std::endl; // 输出 3std::cout << gcd(0, 5) << std::endl;    // 输出 5std::cout << gcd(0, 0) << std::endl;     // 输出 0（特殊处理）return 0;
}

2. 迭代实现

#include <iostream>
#include <cstdlib>int gcd_iter(int a, int b) {a = abs(a);b = abs(b);while (b != 0) {int temp = a % b;a = b;b = temp;}return a;
}int main() {std::cout << gcd_iter(48, 18) << std::endl;  // 输出 6std::cout << gcd_iter(0, 5) << std::endl;    // 输出 5return 0;
}

关键点

  • 处理负数：通过 abs 确保参数非负。

  • 处理 0：gcd(0, 0) 通常返回 0，但数学上可能未定义，需根据需求处理。

6、扩展应用

  1. 多个数的 GCD：
    递归计算 gcd(a, gcd(b, c))。

  2. 最小公倍数（LCM）：
    利用公式 lcm(a, b) = |a·b| / gcd(a, b)。

  3. 扩展欧几里得算法：
    求解贝祖系数（x, y）及线性方程 ax + by = gcd(a, b)。

7、总结

  • 欧几里得算法是计算 GCD 的最高效方法。

  • 实际应用中需注意处理负数、0 及大数问题。

  • GCD 是数论和密码学的基础，广泛应用于模运算、分数化简等场景。

二、最小公倍数（LCM） 

1、LCM 的定义

        最小公倍数（Least Common Multiple，LCM）指两个或多个整数共有倍数中最小的一个。例如，4 和 6 的倍数分别是 4, 8, 12, 16, ... 和 6, 12, 18, ...，它们的最小公倍数是 12，因此 lcm(4, 6) = 12。

2、LCM 的性质

  1. 交换律：lcm(a, b) = lcm(b, a)

  2. 结合律：lcm(a, lcm(b, c)) = lcm(lcm(a, b), c)

  3. 与 GCD 的关系：lcm(a, b) = |a·b| / gcd(a, b)

  4. 与倍数的关系：

    • 若 a 整除 b，则 lcm(a, b) = |b|

    • lcm(ka, kb) = |k|·lcm(a, b)（k 为整数）

  5. 分配律：lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

3、LCM 的计算方法

1. 基于 GCD 的计算

利用 LCM 与 GCD 的关系公式：

这是计算 LCM 的最常用方法。

2. 直接枚举法

从小到大枚举 a 和 b 的倍数，找到第一个共同的倍数。这种方法效率较低，仅适用于小整数。

4、C++ 实现

1. 基于 GCD 的实现

#include <iostream>
#include <cstdlib> // 用于 abs 函数// 计算 GCD
int gcd(int a, int b) {if (b == 0)return abs(a);return gcd(b, a % b);
}// 计算 LCM
int lcm(int a, int b) {if (a == 0 || b == 0)return 0; // 特殊情况处理return abs(a * b) / gcd(a, b);
}int main() {std::cout << lcm(4, 6) << std::endl;    // 输出 12std::cout << lcm(12, 18) << std::endl;  // 输出 36std::cout << lcm(0, 5) << std::endl;    // 输出 0std::cout << lcm(-4, 6) << std::endl;   // 输出 12return 0;
}

2. 直接枚举法实现

#include <iostream>
#include <algorithm> // 用于 max 函数int lcm_enum(int a, int b) {int max_num = std::max(a, b);while (true) {if (max_num % a == 0 && max_num % b == 0)return max_num;max_num++;}
}int main() {std::cout << lcm_enum(4, 6) << std::endl;   // 输出 12std::cout << lcm_enum(12, 18) << std::endl; // 输出 36return 0;
}

5、扩展应用

  1. 多个数的 LCM：
    递归计算 lcm(a, lcm(b, c))。

  2. 分数运算：
    在分数加减法中，LCM 用于通分。

  3. 周期性任务调度：
    在计算任务周期时，LCM 可用于确定任务的最小重复周期。

6、总结

  • LCM 与 GCD 的关系是计算 LCM 的核心。

  • 基于 GCD 的计算方法效率高，适用于大多数场景。

  • 实际应用中需注意处理负数、0 及大数问题。

  • LCM 在数学、计算机科学和工程中有广泛应用。

7、示例问题

问题：计算 12、18 和 24 的最小公倍数。
解法：

  1. 计算 gcd(12, 18) = 6，lcm(12, 18) = (12 * 18) / 6 = 36。

  2. 计算 gcd(36, 24) = 12，lcm(36, 24) = (36 * 24) / 12 = 72。

  3. 最终结果为 72。

C++ 实现：

#include <iostream>
#include <cstdlib>int gcd(int a, int b) {if (b == 0)return abs(a);return gcd(b, a % b);
}int lcm(int a, int b) {if (a == 0 || b == 0)return 0;return abs(a * b) / gcd(a, b);
}int lcm_multiple(int arr[], int n) {int result = 1;for (int i = 0; i < n; i++) {result = lcm(result, arr[i]);}return result;
}int main() {int arr[] = {12, 18, 24};int n = sizeof(arr) / sizeof(arr[0]);std::cout << lcm_multiple(arr, n) << std::endl; // 输出 72return 0;
}

http://www.ppmy.cn/devtools/167269.html

相关文章

【AI论文】MM-Eureka：基于规则的大规模强化学习探索视觉“啊哈”时刻

【AI论文】MM-Eureka：基于规则的大规模强化学习探索视觉“啊哈”时刻

摘要&#xff1a;我们提出了MM-Eureka&#xff0c;这是一个多模态推理模型&#xff0c;成功地将基于规则的大规模强化学习&#xff08;RL&#xff09;扩展到多模态推理领域。虽然基于规则的RL在提升大型语言模型&#xff08;LLMs&#xff09;在文本领域的推理能力方面已经取得了…
阅读更多...
Qt项目中集成第三方模块的.pri文件

Qt项目中集成第三方模块的.pri文件

对于功能模块较多的Qt项目&#xff0c;使用pri文件管理模块文件&#xff0c;降低工程复杂度&#xff0c;提高软件模块的封装性和重用性。 一、.pro与.pri 对于模块化编程&#xff0c;Qt提供了pro和pri&#xff0c;pro管理项目&#xff0c;pri管理模块。 .pro 文件是Qt项目的…
阅读更多...
TDengine 使用最佳实践

TDengine 使用最佳实践

简介 阅读本文档需要具备的基础知识&#xff1a; Linux系统的基础知识&#xff0c;及基本命令网络基础知识&#xff1a;TCP/UDP、http、RESTful、域名解析、FQDN/hostname、hosts、防火墙、四层/七层负载均衡 本文档的阅读对象有&#xff1a;架构师、研发工程师&#xff0c;…
阅读更多...
Python 推导式详解

Python 推导式详解

Python 推导式详解 Python 推导式&#xff08;Comprehension&#xff09;是一种简洁高效的语法结构&#xff0c;用于快速生成列表、字典、集合等数据结构。它通过一行代码替代传统的多行循环&#xff0c;使代码更简洁易读。以下是常见的推导式类型及用法详解&#xff1a; 一、…
阅读更多...
C#设计模式Demo——MVC

C#设计模式Demo——MVC

设计模式Demo——MVC 1.View1.1页面示例1.2View代码1.3修改界面以及代码 2.Model3.Controller4.数据结构5枚举类型6.工具类6.1缓存信息6.2扩展类. 文件结构图 1.View 1.1页面示例 1.2View代码 using System; using System.Data; using System.Windows.Forms; using MVC模式…
阅读更多...
词向量：优维大模型语义理解的深度引擎

词向量：优维大模型语义理解的深度引擎

★ 放闸溯源 优维大模型「骨架级」技术干货 第二篇 ⇓ 词向量是Transformer突破传统NLP技术瓶颈的核心&#xff0c;它通过稠密向量空间映射&#xff0c;将离散符号转化为连续语义表示。优维大模型基于词向量技术&#xff0c;构建了运维领域的“语义地图”&#xff0c;实现从…
阅读更多...
便捷开启 PDF 功能之旅，绿色软件随心用

便捷开启 PDF 功能之旅，绿色软件随心用

软件介绍 以往给大家推荐 DC 时&#xff0c;多是安装版本&#xff0c;这次可不一样&#xff0c;带来的是 DC 绿色版本&#xff0c;无需繁琐安装步骤&#xff0c;只需双击 exe 文件&#xff0c;就能快速打开软件&#xff0c;开启便捷的 PDF 处理之旅。 DC 这款软件功能极其丰富…
阅读更多...
边缘计算（Edge Computing）

边缘计算（Edge Computing）

边缘计算&#xff08;Edge Computing&#xff09;是一种分布式计算范式&#xff0c;它将数据处理和存储功能从传统的集中式云端转移到靠近数据源的网络边缘设备&#xff08;如路由器、网关、本地服务器或终端设备&#xff09;。边缘计算的目标是减少数据传输延迟、降低带宽压力…
阅读更多...
最新文章

Copyright @ 2022~2023