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

【编程基础】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>nr=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, 假设 dddm,nm, nm,n 的一个公约数,即 mmmnnn 都可以被 ddd 整除。
r=m−knr=m-k nr=mkn,两边同时除以 ddd ,可得:
rd=md−knd=h\frac{r}{d}=\frac{m}{d}-\frac{k n}{d}=h dr=dmdkn=h
由等式右边可知 hhh 为整数( dddmmmnnn 的公约数, knk nknnnn 的整倍数,所以 knd\frac{k n}{d}dkn 也应该是整数),所 以我们得出 ddd 也为 mmmnnn 的余数的公约数即 dddn,mmodnn , m \bmod nnmmodn 的公约数
至此,我们得知,如果一个数是两个数的公约数,那么,它也是这两个数的余数和较小数公约数。
假设 ddd(n,mmodn)(n, m \bmod n)(n,mmodn) 的任意一个公约数,则 dddnnn 的公约数, ddd(m−kn)(m-k n)(mkn) 的公约数, kkk 是一个整数,
我们假设 n=xd,m−kn=ydn=x d, m-k n=y dn=xd,mkn=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 为正整数, dddmmm 的公约数, knd\frac{k n}{d}dkn 也肯定是正整数,故得 dddmmm 的公约数.
因为 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&#xff0c;求其最大公约数和最小公倍数。 输入格式 两个整数 输出格式 最大公约数&#xff0c;最小公倍数 样例输入 5 7 样例输出 1 35 题目思路 在这里我们用m表示较大的那个数&#xff0c;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 周五&#x1f48c;发音小贴士&#xff1a;&#x1f48c;当日目标音发音规则/技巧:&#x1f36d; Part 1【热身练习】&#x1f36d; Part2【练习内容】&#x1f36d;【练习感受】&#x1f353;元音 [ɑ:]…...

LabVIEW中以编程方式获取VI克隆名称

LabVIEW中以编程方式获取VI克隆名称演示如何以编程方式获取VI的名称或克隆名称。如果VI作为顶级VI运行&#xff0c;则将显示VI的名称。如果VI在主VI中用作子VI&#xff0c;它将返回克隆的名称。在项目开发过程中&#xff0c;有时需要获取VI的名称。在此示例中&#xff0c;实现了…...

Mysql count(*)的使用原理以及InnoDb的优化策略

Mysql count的原理你真的了解吗&#xff1f;1、数据库引擎的区别2、InnoDB中count的使用3、innodb对select(\*)的优化/为什么select(\*)通过非聚集索引效率要高于聚集索引面试问到说“你觉得count(*) 的效率怎么样&#xff1f;”&#xff0c;一般回复innodb对count(*)进行优化后…...

一文入门HTML+CSS+JS(样例后续更新)

一文入门HTMLCSSJS&#xff08;样例后续更新&#xff09;前言HTML&#xff0c;CSS和JS的关系HTMLhead元素titlelinkmetabody元素设置网页正文颜色与背景颜色添加网页背景图片设置网页链接文字颜色设置网页边框文字与段落标记普通文字的输入对文字字体的设置 font使用文字的修饰…...

【STL】Vector剖析及模拟实现

✍作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;C vector的常用接口 首先贴上&#xff1a;vector的文档介绍,以备查阅使用。 vector的基本框架&#xff1a; vector的成员变量分别是空间首部分的_start指针和最后一个元素的下一个位置的_finish指针&#xff0c;以…...

数据库建表的一些技巧

文章目录 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. 线程 定义&#xff1a;线程是进程的组成部分&#xff0c;不同的线程执行不同的任务&#xff0c;不同的功能模块&#xff0c;同时线程使用的资源师由进程管理&#xff0c;主要分配CPU和内存。 ​ 在进程中&#xff0c;线程执行的方式是抢占式执行操作&#xff0c;需要考…...

[深入理解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 可以一起…...

计算机网络(第八版)——第一章知识总结

本笔记来源于博主上课所记笔记整理&#xff0c;可能不全&#xff0c;欢迎大家批评指正&#xff0c;如果觉得有用记得点个赞&#xff0c;给博主点个关注...该笔记将会持续更新...整理不易&#xff0c;希望大家多多点赞。 第一章 计算机网络体系结构 1.计算机网络的作用 1.1互…...

Linux学习笔记

前段时间看了网课&#xff1a;https://www.bilibili.com/video/BV1mW411i7Qf?spm_id_from333.337.search-card.all.click&vd_source7b9f1ca2783a4c39a4d640a31e23457e 记了一些笔记&#xff0c;先放到这里&#xff0c;后面慢慢整理&#xff1a; 内存分配&#xff1a;分区…...

树与二叉树(概念篇)

树与二叉树1 树的概念1.1 树的简单概念1.2 树的概念名词1.3 树的相关表示2 二叉树的概念2.1 二叉树的简单概念2.1.1 特殊二叉树2.2 二叉树的性质2.3 二叉树的存储结构1 树的概念 1.1 树的简单概念 树是一种非线性的数据结构&#xff0c;它是由n(n>0)个有限节点组成的一个具…...

C++回顾(二十五)—— map/multimap容器

25.1 map/multimap的简介 map是标准的关联式容器&#xff0c;一个map是一个键值对序列&#xff0c;即(key,value)对。它提供基于key的快速检索能力。map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入&#xff0c;所以不能指定插入位置。map的…...

7.3 向量的数量积与向量积

&#x1f64c;作者简介&#xff1a;数学与计算机科学学院出身、在职高校高等数学专任教师&#xff0c;分享学习经验、生活、 努力成为像代码一样有逻辑的人&#xff01; &#x1f319;个人主页&#xff1a;阿芒的主页 ⭐ 高等数学专栏介绍&#xff1a;本专栏系统地梳理高等数学…...

Qt静态扫描(命令行操作)

Qt静态扫描&#xff08;命令行操作&#xff09; 前沿&#xff1a; 静态代码分析是指无需运行被测代码&#xff0c;通过词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描&#xff0c;找出代码隐藏的错误和缺陷&#xff0c;如参数不匹配&#xff0c;有歧义的嵌…...

【Hadoop】配置文件

Hadoop 配置文件分两类&#xff1a;默认配置文件和自定义配置文件&#xff0c;只有用户想修改某一默认 配置值时&#xff0c;才需要修改自定义配置文件&#xff0c;更改相应属性值 &#xff08;1&#xff09;默认配置文件&#xff1a; cd $HADOOP_HOME/share/hadoop common路…...

python进程池

Python进程池是Python标准库中multiprocessing模块提供的一种用于管理进程的方式。它可以使Python程序以并行的方式执行任务&#xff0c;提高程序的运行效率。本篇博客将介绍如何使用Python进程池。 创建进程池 在使用Python进程池之前&#xff0c;我们需要先创建一个进程池对…...

笔记本固态盘数据丢失怎么办?笔记本固态盘怎么恢复数据

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

堆的结构与实现

堆的结构与实现二叉树的顺序结构堆的概念及结构堆的实现堆的创建向上调整建堆向下调整建堆堆的操作链接二叉树的顺序结构 堆其实是具有一定规则限制的完全二叉树。 普通的二叉树是不太适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树会更适合使用顺…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...