【编程基础】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进程池之前,我们需要先创建一个进程池对…...

笔记本固态盘数据丢失怎么办?笔记本固态盘怎么恢复数据
如果笔记本固态盘数据丢失怎么办?笔记本固态盘怎么恢复数据?下面将为大家详细地介绍一下笔记本固态硬盘数据恢复的三种实用方法,希望对大家有所帮助。一、简单恢复方法笔记本固态硬盘数据删除以后,较为简单直接的恢复方法就是从回…...

堆的结构与实现
堆的结构与实现二叉树的顺序结构堆的概念及结构堆的实现堆的创建向上调整建堆向下调整建堆堆的操作链接二叉树的顺序结构 堆其实是具有一定规则限制的完全二叉树。 普通的二叉树是不太适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树会更适合使用顺…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...

Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...