【数据结构与算法】最大公约数与最小公倍数

最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）是数学词汇，指能够整除多个非零整数的最大正整数。例如8和12的最大公因数为4。表示：gcd(8,12) = 4

最小公倍数（英语：least common multiple，lcm）是数论中的一个概念。若有一个数X，可以被另外两个数A,B整除，且X同时大于或等于A和B，则X为A和B的公倍数。A和B的公倍数有无限个，而所有正的公倍数中，最小的公倍数就叫做最小公倍数。例如8和12的最小公倍数为24。表示：lcm(8,12) = 24

两个整数的最小公倍数与最大公因数之间有如下的关系：

公式

根据上面的示例：|8*12|/4=24

也就是说，我们掌握了最大公约数的求法，也就能求最小公倍数

那么我们就以最大公约数为例

枚举(穷举)

根据已有的数学知识我们知道，m>n的话，m,n的最大公约数永远不可能是m（因为n/m不能整除），最大只可能是n。所以我们只需要从n开始依次向较小数找到“能同时被n,m整除的第一个整数”即为两数的最大公约数。

代码示例：

#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    int i;
    int gcd;
    gcd = 1;
    for(i = (a<b?a: b); i > 0; i--)
    {
        if(a % i == 0 && b % i == 0)
        {
            gcd = i;
            break;
        }
    }
    printf("gcd = %d\n", gcd);
    return 0;
}

另一种穷举原理：

求出两数的所有公因子，再把公因子累乘得到最大公约数。

代码示例：

#include <iostream>
using namespace std;
int CommFactor2(int m, int n); 
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为：" << CommFactor2(a,b)<< endl;
  return 0;
}
int CommFactor2(int m,int n)
{
  int i;
  int factor = 1;
  for (i=2;i<=m&&i<<n;i++)
  {
    while(m % i == 0 && n % i == 0)  //这里不能用if语句，因为可能会有重复的公因子
    {
      factor = factor * i;
      m = m / i;
      n = n / i;
    }
  }
  return factor;
}

辗转相除法

辗转相除法，又称欧几里得算法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。表示：gcd(a,b) = gcd(b,a mod b) (a>b)

辗转相除法

代码示例：

#include <stdio.h>
int main(int argc, const char* argv[])
{
    int a,b,temp;
    scanf("%d %d", &a, &b);
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    printf("gcd = %d\n", a);
    return 0;
}

更相减损法

更相减损法，又称辗转相减法。更相减损法出自《九章算术》：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”(原本是为了约分而设计的)

具体方法为两个数之间大的数字减小的数字，之后将得到的差作为减数，较小的数作为被减数，再次相减，直到与所得的差相同，此时的差即为两个数之间的最大公约数。

用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，k*a+b)，其中a、b、k都为自然数。

基于上面的原理，就能实现我们的迭代相减法：(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2

代码示例：

#include<iostream>
using namespace std;
int gcd(int a, int b)
{
    while(a != b)
        if(a > b) a -= b;
        else b -= a;
    return a;
}
int main(){
	int m,n;
	cin>>m>>n;
	cout<<"gcd:"<<gcd(m,n)<<endl;
	return 0;
}

Stein算法

Stein算法是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。

欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来：一般实际应用中的整数很少会超过64位（当然现在已经允许128位了），对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，比如说RSA加密算法至少要求500bit密钥长度，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法很好的解决了欧几里德算法中的这个缺陷，Stein算法只有整数的移位和加减法。下面就来说一下Stein算法的原理：

  1. 若a和b都是偶数，则记录下公约数2，然后都除2（即右移1位）
  2. 若其中一个数是偶数，则偶数除2，因为此时2不可能是这两个数的公约数了
  3. 若两个都是奇数，则a = |a-b|，b = min(a,b)，因为若d是a和b的公约数，那么d也是|a-b|和min(a,b)的公约数
这里对3.进行简单的证明：
不妨设奇数A>B，A和B的公约数为X，即A=jX，B=kX，其中j，k均为正整数且j>k。
A−B=(j−k)X
因为j，k均为整数，所以X也是A-B的公约数。
min(A,B)=B
所以A-B与min(A,B)公约数相同，因为A，B都是奇数，所以A-B必然是偶数，偶数又可以二除移位了。

代码示例1：

#include<iostream>
using namespace std;
int SteinGCD(int a, int b) {
    if (a < b) { int t = a; a = b; b = t; }
    if (b == 0) return a;
    if ((a & 1) == 0 && (b & 1) == 0)
        return SteinGCD(a >> 1, b >> 1) << 1;
    else if ((a & 1) == 0 && (b & 1) != 0)
        return SteinGCD(a >> 1, b);
    else if ((a & 1) != 0 && (b & 1) == 0)
        return SteinGCD(a, b >> 1);
    else
        return SteinGCD(a - b, b);
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<"gcd:"<<SteinGCD(m,n)<<endl;
    return 0;
}

代码示例2：

#include<iostream>
using namespace std;
int gcd(int u, int v)
{
    if (u == 0)	return v;
    if (v == 0)	return u;
    if (~u & 1)
    {
        if (v & 1)
            return gcd(u >> 1, v);
        else
            return gcd(u >> 1, v >> 1) << 1;
    }
    if (~v & 1)
        return gcd(u, v >> 1);
    if (u > v)
        return gcd((u - v) >> 1, v);
    return gcd((v - u) >> 1, u);
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<"gcd:"<<gcd(m,n)<<endl;
    return 0;
}

Stein算法非递归方式

代码示例：

#include<iostream>
using namespace std;
int SteinGCD(int a, int b) {
    int acc = 0;
    while ((a & 1) == 0 && (b & 1) == 0) {
        acc++;
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0) a >>= 1;
    while ((b & 1) == 0) b >>= 1;
    if (a < b) { int t = a; a = b; b = t; }
    while ((a = (a - b) >> 1) != 0) {
        while ((a & 1) == 0) a >>= 1;
        if (a < b) { int t = a; a = b; b = t; }
    }
    return b << acc;
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<"gcd:"<<SteinGCD(m,n)<<endl;
    return 0;
}

库函数

__gcd(a,b)——库algorithm

注意：gcd前面有两个下划线

gcd(a,b)——库numeric

注意：仅作扩展，如无必要，不要使用

位运算

利用位运算的特性，将两数交换改成位运算。
inline可加可不加。我实际试验中，在1e8次执行后，加与不加的时间差在80ms左右，而两者本来的运行时间均在3000ms上下，即差别不大

代码示例：

inline int gcd(int a, int b)
{
    while(b ^= a ^= b ^= a %= b);    
    return a;
}

利用取模特点

很快，几乎与__gcd(a,b)的时间一致

代码示例：

int gcd(int a, int b){
    if(!a || !b)
        return max(a, b);
    for(int t; t = a % b; a = b, b = t);
    return b;
}

以上方法都为最大公约数的求法，若要求最小公倍数，利用关系计算即可。

迭乘法(求最小公倍数)

由公倍数的定义出发，如果一个数k是a和b的公倍数，那么k可以表示成 a*m或 b*n，而当(a*m) % b == 0时，k是最小公倍数

代码示例：

#include<stdio.h>
int main(){
    int a,b;
    scanf("%d %d", &a, &b);
    int i = 1;
    while((a*i) % b != 0){
        i++;
    }
    printf("最小公倍数是：%d\n", a * i);
    return 0;
}

参考博文：

https://blog.csdn.net/Hsuesh/article/details/111992593

https://blog.csdn.net/ly_6699/article/details/90719315

https://blog.csdn.net/JH13thpig/article/details/124362053

https://blog.csdn.net/weq2011/article/details/127953257

https://blog.csdn.net/Holmofy/article/details/76401074

https://blog.csdn.net/wyd_333/article/details/126111037

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

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

相关文章

Linux系统部署可视化数据多维表格APITable并实现无公网IP远程协同办公

Linux系统部署可视化数据多维表格APITable并实现无公网IP远程协同办公

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-G5XdKx1vxX0o0PES {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
说说你对集合的理解？常见的操作有哪些？

说说你对集合的理解？常见的操作有哪些？

一、是什么 集合&#xff08;Set&#xff09;&#xff0c;指具有某种特定性质的事物的总体&#xff0c;里面的每一项内容称作元素 在数学中&#xff0c;我们经常会遇到集合的概念&#xff1a; 有限集合&#xff1a;例如一个班集所有的同学构成的集合无限集合&#xff1a;例如…
阅读更多...
上网方法介绍

上网方法介绍

注册 https://www.cordcloud.biz/user 注册后先充值&#xff0c;充值后还要购买套餐&#xff0c; 充值之后&#xff0c;就可以看到流量了&#xff0c;然后复制订阅地址&#xff0c;到客户端去自动下载 URL拷贝到这个地方&#xff0c;然后点击下载
阅读更多...
latex论文写作学习

latex论文写作学习

首先无论是什么文章&#xff0c;最基础的格式都是这个&#xff1a; 如何修改字体呢&#xff1f;&#xff1a; 这样一来就可以在写完之后统一改掉了&#xff0c;用来做标记 最后记得\par 插图&#xff1a; 命令后面的中括号一般就是option
阅读更多...
ESP32S3学习笔记（0）—— Vscode IDF环境搭建及OpenOCD调试介绍

ESP32S3学习笔记（0）—— Vscode IDF环境搭建及OpenOCD调试介绍

前言 &#xff08;1&#xff09;如果有嵌入式企业需要招聘湖南区域日常实习生&#xff0c;任何区域的暑假Linux驱动/单片机/RTOS的实习岗位&#xff0c;可C站直接私聊&#xff0c;或者邮件&#xff1a;zhangyixu02gmail.com&#xff0c;此消息至2025年1月1日前均有效 &#xff…
阅读更多...
男生穿什么裤子最百搭？适合男生穿的裤子品牌测评分享

男生穿什么裤子最百搭？适合男生穿的裤子品牌测评分享

每个伙伴们想必经常都会选择一些裤子&#xff0c;但现在市面上的裤子品牌也实在太多了&#xff0c;好不容易选到了几件好看的裤子&#xff0c;结果质量却很不好。主要就是因为现在有太多商家为了利润而使用一些舒适性、质量差的面料&#xff0c;那么今天就给大家分享一些质量上…
阅读更多...
实战小项目 | ESP32-S3和ESP32-C3通过ESP-Mesh-Lite组网 温湿度传感器案例

实战小项目 | ESP32-S3和ESP32-C3通过ESP-Mesh-Lite组网 温湿度传感器案例

传统Wi-Fi网络所有终端设备都需要直接与路由器相连&#xff0c;这使得Wi-Fi的覆盖区域受到路由器位置的限制&#xff0c;可接入终端设备的数量也受到路由器容量的限制。而乐鑫ESP-Mesh-Lite Wi-Fi组网方案&#xff0c;所有终端设备都可以与相邻设备连接&#xff0c;摆脱了对路由…
阅读更多...
酒店水电能源计量管理系统

酒店水电能源计量管理系统

酒店水电能源计量管理系统是一种针对酒店行业设计的能源管理系统&#xff0c;旨在实现对水电能源的计量、监测和管理。本文将从系统特点、构成以及带来的效益三个方面展开介绍。 系统特点 1.多元化计量&#xff1a;该系统能够对酒店内的水、电能源进行多元化计量&#xff0c;…
阅读更多...
【C++学习】map和set

【C++学习】map和set

目录 一、关联式容器 二、键值对 三、树形结构的关联式容器 四、set 4.1 set的介绍 4.2 set的使用 4.2.1 set的模板参数列表 4.2.2 set的构造 4.2.3 set的容量 4.2.4 set修改操作 4.2.5 set的使用举例 五、map 5.1 map的介绍 5.2 map的使用 5.2.1 map的模板参数说…
阅读更多...
【Qt 学习笔记】Qt常用控件 | 按钮类控件Check Box的使用及说明

【Qt 学习笔记】Qt常用控件 | 按钮类控件Check Box的使用及说明

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 按钮类控件Check Box的使用及说明 文章编号&#xff1a;…
阅读更多...
自动化测试-如何优雅实现方法的依赖

自动化测试-如何优雅实现方法的依赖

在复杂的测试场景中&#xff0c;常常会存在用例依赖&#xff0c;以一个接口自动化平台为例&#xff0c;依赖关系&#xff1a; 创建用例 --> 创建模块 --> 创建项目 --> 登录。 用例依赖的问题 • 用例的依赖对于的执行顺序有严格的要求&#xff0c;比如让被依赖的方…
阅读更多...
揭秘智慧礼品背后的故事

揭秘智慧礼品背后的故事

如若不是从事技术行业&#xff0c;在罗列礼品清单时&#xff0c;可能不会想到 “数据”&#xff0c;但幸运的是&#xff0c;我们想到了。如何将AI技术应用到当季一些最受青睐的产品中去&#xff0c;训练数据是这一智能技术的背后动力。很多电子设备或名称中带有“智能”一词的设…
阅读更多...
TikTok赚钱攻略 | 这6个方法你必须知道

TikTok赚钱攻略 | 这6个方法你必须知道

在浩瀚的网络世界中&#xff0c;TikTok成为了一个让普通人一夜成名的舞台。Khabane Lame和Charli DAmelio就是其中的明星例子。无论是Khabane简单的肢体幽默还是Charli的舞蹈视频&#xff0c;他们都凭借TikTok赚钱&#xff0c;并且成功转变了自己的人生轨迹。他们的故事证明&am…
阅读更多...
【kafka】安装

【kafka】安装

也是第二次安装&#xff0c;蛮记录一下 1.安装kafka之前需要先完成zookeeper的安装 【zookeeper】安装 2. Apache Kafka官网下载 3. 解压完成后修改server.properties配置文件 修改日志文件存放路径 查看与zookeeper连接的端口是否和zookeeper服务所在的端口一致 &#xf…
阅读更多...
BTI性能开销权衡及优化措施

BTI性能开销权衡及优化措施

BTI分支目标识别精讲与实践系列 思考 1、什么是代码重用攻击&#xff1f;什么是ROP攻击&#xff1f;区别与联系&#xff1f; 2、什么是JOP攻击&#xff1f;间接分支跳转指令&#xff1f; 3、JOP攻击的缓解技术&#xff1f;控制流完整性保护&#xff1f; 4、BTI下的JOP如何…
阅读更多...
智能助手大比拼！5款热门思维导图软件细致评估！

智能助手大比拼！5款热门思维导图软件细致评估！

思维导图是一种创造性的方法&#xff0c;集思广益&#xff0c;寻找不同想法之间的联系。如果你做得好&#xff0c;你可以为难题提出新的想法和解决方案&#xff0c;总结一篇文章或演示稿&#xff0c;让你的想法井然有序。在数字时代&#xff0c;纸质思维导图存在不能随意更改、…
阅读更多...
Nginx内存池相关源码剖析（六）外部资源释放和内存池销毁

Nginx内存池相关源码剖析（六）外部资源释放和内存池销毁

ngx_destroy_pool函数 先执行回调函数释放所有的外部资源&#xff0c;然后free释放所有的大块内存和小块内存。 // 释放外部资源&#xff0c;销毁内存池 void ngx_destroy_pool(ngx_pool_t *pool) {ngx_pool_t *p, *n;ngx_pool_large_t *l;ngx_pool_cleanup_t *…
阅读更多...
[数据结构]——二叉树——堆排序

[数据结构]——二叉树——堆排序

后续代码以此为基础 typedef int HPDataTyp; typedef struct Heap {HPDataTyp * a; int size; int capacity; } Hp; 1.首先我们需要掌握两种堆算法 1&#xff0c;堆向下调整算法 现在我们给出一个数组&#xff0c;逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整…
阅读更多...
清明三天，用Python赚了4万？

清明三天，用Python赚了4万？

每年4月&#xff0c;是Python圈子里接私活的旺季&#xff0c;特别是在节假日这种数据暴增的时间段&#xff0c;爬虫采集、逆向破解类的私活订单会集中爆发&#xff0c;量大价高。几乎所有的圈内人都在趁着旺季接私活。 正好&#xff0c;我昨天就做了一单爬虫逆向私活&#xff…
阅读更多...
社科院与新加坡社科大学工商管理博士——结合顶尖学术力量，培养全球战略领导力

社科院与新加坡社科大学工商管理博士——结合顶尖学术力量，培养全球战略领导力

在当今全球化的时代&#xff0c;工商管理博士项目不仅仅是为了培养学术研究者&#xff0c;更是为了孕育出具有全球战略领导力的商业领袖。这样的项目需要顶尖的学术力量来引领&#xff0c;而中国社会科学院与新加坡社科大学正是这样的学术巨擘。两者联合培养的工商管理博士项目…
阅读更多...
最新文章

Copyright @ 2022~2023