【编程基础】009.输入两个正整数m和n,求其最大公约数和最小公倍数。
最大公约数与最小公倍数
题目描述
输入两个正整数m和n,求其最大公约数和最小公倍数。
输入格式
两个整数
输出格式
最大公约数,最小公倍数
样例输入
5 7
样例输出
1 35
题目思路
在这里我们用m表示较大的那个数,n表示较小的数。求最大公约数也即是求能被m和n 整除的最大数。gcd(m,n) 表示m 和n 的最大公约数。根据辗转相除法可知gcd(m,n)=gcd(n,m%n),具体证明过程如下:
gcd(m,n)=gcd(n,mmodn)\operatorname{gcd}(m, n)=\operatorname{gcd}(n, m \bmod n)gcd(m,n)=gcd(n,mmodn) (不妨设 m>nm>nm>n 且 r=mmodn,r≠0r=m \bmod n, r \neq 0r=mmodn,r=0 )
mmm 可以表示成 m=kn+r(m,n,k,rm=k n+r(m, n, k, rm=kn+r(m,n,k,r 皆为正整数, 且 r<n)r<n)r<n) ,则 r=mmodnr=m \bmod nr=mmodn, 假设 ddd 是 m,nm, nm,n 的一个公约数,即 mmm 和 nnn 都可以被 ddd 整除。
而 r=m−knr=m-k nr=m−kn,两边同时除以 ddd ,可得:
rd=md−knd=h\frac{r}{d}=\frac{m}{d}-\frac{k n}{d}=h dr=dm−dkn=h
由等式右边可知 hhh 为整数( ddd 是 mmm 和 nnn 的公约数, knk nkn 是 nnn 的整倍数,所以 knd\frac{k n}{d}dkn 也应该是整数),所 以我们得出 ddd 也为 mmm 和 nnn 的余数的公约数即 ddd 是 n,mmodnn , m \bmod nn,mmodn 的公约数
至此,我们得知,如果一个数是两个数的公约数,那么,它也是这两个数的余数和较小数公约数。
假设 ddd 是 (n,mmodn)(n, m \bmod n)(n,mmodn) 的任意一个公约数,则 ddd 是 nnn 的公约数, ddd 是 (m−kn)(m-k n)(m−kn) 的公约数, kkk 是一个整数,
我们假设 n=xd,m−kn=ydn=x d, m-k n=y dn=xd,m−kn=yd 其中 x,yx, yx,y 是正整数,根据上面的推断可得:
m=yd+knm=y d+k n m=yd+kn
两边同时除以 ddd ,得
md=y+knd\frac{m}{d}=y+\frac{k n}{d} dm=y+dkn
由已知可得 yyy 为正整数, ddd 是 mmm 的公约数, knd\frac{k n}{d}dkn 也肯定是正整数,故得 ddd 为 mmm 的公约数.
因为 ddd 既是 nnn 的公约数又是 mmm 的公约数了,
所以证出 (m,n)(m, n)(m,n) 和 (n,mmodn)(n, m \bmod n)(n,mmodn) 的公约数是一样的,其最大公约数也必然相等。
所以求m和n的最大公约数,等价于求n 和m%n的最大公约数,用图来表示即不断地用n去填充 m表示的区域,接着赋值n=m%n,m=n 重复上述操作直到m%n==0,则n就是m和n的最大公约数。

AC代码(C语言)
#include<stdio.h>
int gcd(int m,int n){ int t;if(n>m){//令m>nt=n;n=m;m=t;}if(m%n==0) return n;return gcd(n,m%n);
}
int main(){int m,n;scanf("%d%d",&m,&n);int gc=gcd(m,n);int cm=(m/gc)*(n/gc)*gc;printf("%d\n%d\n",gc,cm);return 0;
}
相关文章:
【编程基础】009.输入两个正整数m和n,求其最大公约数和最小公倍数。
最大公约数与最小公倍数 题目描述 输入两个正整数m和n,求其最大公约数和最小公倍数。 输入格式 两个整数 输出格式 最大公约数,最小公倍数 样例输入 5 7 样例输出 1 35 题目思路 在这里我们用m表示较大的那个数,n表示较小的数。求…...
Golang错误处理
介绍 如果你写过任何 Go 代码,你可能遇到过内置error类型。Go 代码使用error值来指示异常状态。例如,函数在打开文件失败时os.Open返回一个非零值。error func Open(name string) (file *File, err error) 下面的代码用于os.Open打开一个文件。如果发生错误,它会调用log.Fat…...
English Learning - L2 语音作业打卡 复习对比 [ɑ:] [æ] Day18 2023.3.10 周五
English Learning - L2 语音作业打卡 复习对比 [ɑ:] [] Day18 2023.3.10 周五💌发音小贴士:💌当日目标音发音规则/技巧:🍭 Part 1【热身练习】🍭 Part2【练习内容】🍭【练习感受】🍓元音 [ɑ:]…...
LabVIEW中以编程方式获取VI克隆名称
LabVIEW中以编程方式获取VI克隆名称演示如何以编程方式获取VI的名称或克隆名称。如果VI作为顶级VI运行,则将显示VI的名称。如果VI在主VI中用作子VI,它将返回克隆的名称。在项目开发过程中,有时需要获取VI的名称。在此示例中,实现了…...
Mysql count(*)的使用原理以及InnoDb的优化策略
Mysql count的原理你真的了解吗?1、数据库引擎的区别2、InnoDB中count的使用3、innodb对select(\*)的优化/为什么select(\*)通过非聚集索引效率要高于聚集索引面试问到说“你觉得count(*) 的效率怎么样?”,一般回复innodb对count(*)进行优化后…...
一文入门HTML+CSS+JS(样例后续更新)
一文入门HTMLCSSJS(样例后续更新)前言HTML,CSS和JS的关系HTMLhead元素titlelinkmetabody元素设置网页正文颜色与背景颜色添加网页背景图片设置网页链接文字颜色设置网页边框文字与段落标记普通文字的输入对文字字体的设置 font使用文字的修饰…...
【STL】Vector剖析及模拟实现
✍作者:阿润菜菜 📖专栏:C vector的常用接口 首先贴上:vector的文档介绍,以备查阅使用。 vector的基本框架: vector的成员变量分别是空间首部分的_start指针和最后一个元素的下一个位置的_finish指针,以…...
数据库建表的一些技巧
文章目录 1.名字1.1 见名知意1.2 大小写1.3 分隔符1.4 表名1.5 字段名称1.6 索引名2.字段类型3.字段长度4.字段个数5. 主键6.存储引擎7. NOT NULL8.外键9. 索引10.时间字段11.金额字段12.唯一索引13.字符集14. 排序规则15.大字段总结如果我们在建表的时候不注意细节,等后面系统…...
线程(一)
线程 1. 线程 定义:线程是进程的组成部分,不同的线程执行不同的任务,不同的功能模块,同时线程使用的资源师由进程管理,主要分配CPU和内存。 在进程中,线程执行的方式是抢占式执行操作,需要考…...
[深入理解SSD系列 闪存实战2.1.8] NAND FLASH Multi Plane Program(写)操作_multi plane 为何能提高闪存速度
前言 上一篇我们介绍了 [深入理解SSD系列 闪存实战2.1.7] NAND FLASH基本编程(写)操作及原理_NAND FLASH Program Operation 源码实现。这只是一次对单个plane 写, 按这样的话, 要先program plane 0 完成后, 再 program plane 1。 如果我偷偷告诉你, 两个 plane 可以一起…...
计算机网络(第八版)——第一章知识总结
本笔记来源于博主上课所记笔记整理,可能不全,欢迎大家批评指正,如果觉得有用记得点个赞,给博主点个关注...该笔记将会持续更新...整理不易,希望大家多多点赞。 第一章 计算机网络体系结构 1.计算机网络的作用 1.1互…...
Linux学习笔记
前段时间看了网课:https://www.bilibili.com/video/BV1mW411i7Qf?spm_id_from333.337.search-card.all.click&vd_source7b9f1ca2783a4c39a4d640a31e23457e 记了一些笔记,先放到这里,后面慢慢整理: 内存分配:分区…...
树与二叉树(概念篇)
树与二叉树1 树的概念1.1 树的简单概念1.2 树的概念名词1.3 树的相关表示2 二叉树的概念2.1 二叉树的简单概念2.1.1 特殊二叉树2.2 二叉树的性质2.3 二叉树的存储结构1 树的概念 1.1 树的简单概念 树是一种非线性的数据结构,它是由n(n>0)个有限节点组成的一个具…...
C++回顾(二十五)—— map/multimap容器
25.1 map/multimap的简介 map是标准的关联式容器,一个map是一个键值对序列,即(key,value)对。它提供基于key的快速检索能力。map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。map的…...
7.3 向量的数量积与向量积
🙌作者简介:数学与计算机科学学院出身、在职高校高等数学专任教师,分享学习经验、生活、 努力成为像代码一样有逻辑的人! 🌙个人主页:阿芒的主页 ⭐ 高等数学专栏介绍:本专栏系统地梳理高等数学…...
Qt静态扫描(命令行操作)
Qt静态扫描(命令行操作) 前沿: 静态代码分析是指无需运行被测代码,通过词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描,找出代码隐藏的错误和缺陷,如参数不匹配,有歧义的嵌…...
【Hadoop】配置文件
Hadoop 配置文件分两类:默认配置文件和自定义配置文件,只有用户想修改某一默认 配置值时,才需要修改自定义配置文件,更改相应属性值 (1)默认配置文件: cd $HADOOP_HOME/share/hadoop common路…...
python进程池
Python进程池是Python标准库中multiprocessing模块提供的一种用于管理进程的方式。它可以使Python程序以并行的方式执行任务,提高程序的运行效率。本篇博客将介绍如何使用Python进程池。 创建进程池 在使用Python进程池之前,我们需要先创建一个进程池对…...
笔记本固态盘数据丢失怎么办?笔记本固态盘怎么恢复数据
如果笔记本固态盘数据丢失怎么办?笔记本固态盘怎么恢复数据?下面将为大家详细地介绍一下笔记本固态硬盘数据恢复的三种实用方法,希望对大家有所帮助。一、简单恢复方法笔记本固态硬盘数据删除以后,较为简单直接的恢复方法就是从回…...
堆的结构与实现
堆的结构与实现二叉树的顺序结构堆的概念及结构堆的实现堆的创建向上调整建堆向下调整建堆堆的操作链接二叉树的顺序结构 堆其实是具有一定规则限制的完全二叉树。 普通的二叉树是不太适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树会更适合使用顺…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
