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

【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)

本系列博客为个人刷题思路分享,有需要借鉴即可。

1.题目链接:

2.详解思路:
题目描述:输入两个正整数,输出其最大公因数和最小公倍数
一般方法:最大公因数:穷加法;最小公倍数:穷举法。
巧妙方法:最大公因数:辗转相除法;最小公倍数:数学公式。

在这里插入图片描述
下面是一般方法的代码示例:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>int main()
{int a = 0;int b = 0;int GreComDiv = 0;scanf("%d %d", &a, &b);int min = a < b ? a : b;int i = 0;//最大公约数——穷加法for (i = 1; i <= min; i++){if (a % i == 0 && b % i == 0)GreComDiv = i;}int lcm = 0;int max = a > b ? a : b;//最小公倍数——穷乘法for (i = 1;; i++){if (((i * max) % a == 0) && ((i * max) % b == 0)){lcm = i * max;break;}}printf("最大公约数为%d 最小公倍数为%d\n", GreComDiv, lcm);return 0;
}

下面是比较巧妙的方法代码示例:

int main()
{int a = 0;int b = 0;scanf("%d %d", &a, &b);int c = a;int d = b;while (a && b){if (a > b)a %= b;elseb %= a;}int max = a > b ? a : b;//最大公因数int min = c * d / max;//最小公倍数printf("最大公约数为%d 最小公倍数为%d\n", max, min);return 0;
}

具体为什么可以这样搞,可以去B站搜一下辗转相除法相关视频自己看一下。


完。

相关文章:

【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)

本系列博客为个人刷题思路分享&#xff0c;有需要借鉴即可。 1.题目链接&#xff1a; 无 2.详解思路&#xff1a; 题目描述&#xff1a;输入两个正整数&#xff0c;输出其最大公因数和最小公倍数 一般方法&#xff1a;最大公因数&#xff1a;穷加法&#xff1b;最小公倍数&…...

ETL快速拉取物流信息

我国作为世界第一的物流大国&#xff0c;但是在目前的物流信息系统还存在着几大的痛点。主要包括以下几个方面&#xff1a; 数据孤岛&#xff1a;有些物流企业各个部门之间的数据标准不一致&#xff0c;难以实现数据共享和协同&#xff0c;容易导致信息孤岛。 操作繁琐&#x…...

17.1 SpringMVC框架_SpringMVC入门与数据绑定(❤❤)

17.1 SpringMVC框架_SpringMVC入门与数据绑定 1. SpringMVC入门1.1 MVC介绍1.2 环境配置1. 依赖引入2. web配置文件:DispatchServlet配置3. applicationContext.xml配置4. 开发Controller控制器(❤❤)1.3 MVC处理流程图2. Spring MVC数据绑定2.1 URL Mapping2.2 URL Mapping三个…...

Leetcode 11.盛水最多的容器

题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;你不能倾斜容器。…...

《Go 简易速速上手小册》第7章:包管理与模块(2024 最新版)

文章目录 7.1 使用 Go Modules 管理依赖 - 掌舵向未来7.1.1 基础知识讲解7.1.2 重点案例:Web 服务功能描述实现步骤扩展功能7.1.3 拓展案例 1:使用数据库功能描述实现步骤扩展功能7.1.4 拓展案例 2:集成 Redis 缓存功能描述实现步骤...

【论文精读】IBOT

摘要 掩码语言建模(MLM)是一种流行的语言模型预训练范式&#xff0c;在nlp领域取得了巨大的成功。然而&#xff0c;它对视觉Transformer (ViT)的潜力尚未得到充分开发。为在视觉领域延续MLM的成功&#xff0c;故而探索掩码图像建模(MIM)&#xff0c;以训练更好的视觉transforme…...

Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法

Yolo V5在实时视频流中的建筑物与彩钢房检测&#xff1a;性能评估与改进方法 文章目录 Yolo V5在实时视频流中的建筑物与彩钢房检测&#xff1a;性能评估与改进方法概述Yolo V5模型概述建筑物与彩钢房检测的挑战实时视频流处理流程模型性能评估改进方法实验与分析结论与展望 概…...

图——最小生成树实现(Kruskal算法,prime算法)

目录 预备知识&#xff1a; 最小生成树概念&#xff1a; Kruskal算法&#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; Prime算法 &#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; 结语&#xff1a; 预备知识&#xff1a; 连通图&#xff1a;在无向图…...

Unity3D xLua开发环境搭建详解

前言 xLua是一种基于Lua语言的开发框架&#xff0c;可以帮助开发者在Unity3D中使用Lua脚本来开发游戏。 对惹&#xff0c;这里有一个游戏开发交流小组&#xff0c;希望大家可以点击进来一起交流一下开发经验呀&#xff01; 在本文中&#xff0c;我们将详细介绍如何搭建Unity…...

Python笔记-super().init(root)的作用

假设我们有一个名为Animal的父类&#xff0c;它有一个属性color&#xff0c;在其构造函数__init__中被初始化&#xff1a; class Animal:def __init__(self, color):self.color color现在&#xff0c;我们想创建一个Animal的子类&#xff0c;名为Dog。Dog类有自己的属性name&…...

【git 使用】使用 git rebase -i 修改任意的提交信息/合并多个提交

修改最近一次的提交信息的方法有很多&#xff0c;可以参考这篇文章&#xff0c;但是对于之前的提交信息进行修改只能使用 rebase。 修改提交信息 假设我们想修改下面这个提交信息&#xff0c;想把【登录】改成【退出登录】步骤如下 运行 git rebase -i head~3 打开了一个文本…...

【Vue3】toRefs和toRef在reactive中的一些应用

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

力扣精选算法100道——Z字形变换(模拟专题)

目录 &#x1f388;了解题意 &#x1f388;算法原理 &#x1f6a9;先处理第一行和最后一行 &#x1f6a9;再处理中间行 &#x1f388;实现代码 &#x1f388;了解题意 大家看到这个题目的时候肯定是很迷茫的&#xff0c;包括我自己也是搞不清楚题目什么意思&#xff0c;我…...

Elastic Stack--01--简介、安装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1. Elastic Stack 简介为什么要学习ESDB-Engines搜索引擎类数据库排名常年霸榜![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/051342a83f574c8c910cda…...

.NET项目web自动化测试实战——Selenium 2.0

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…...

【Day53】代码随想录之动态规划_买卖股票ⅠⅡ

文章目录 动态规划理论基础动规五部曲&#xff1a;出现结果不正确&#xff1a; 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础 动规五部曲&#xff1a; 确定dp数组 下标及dp[i] 的含义。递推公式&#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初…...

Swift Combine 使用调试器调试管道 从入门到精通二十六

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…...

go内置库函数实现client与server数据的发送接收

功能&#xff1a;客户端持续写入数据&#xff0c;直到输入exit退出&#xff0c;服务端读取数据并打印 注意&#xff1a;server和client目录在同一层级 服务端 server/main package mainimport ("fmt""net" )func main() {listen, err : net.Listen(&quo…...

[java基础揉碎]this

引出this: 什么是this: java虚拟机会给每个对象分配 this&#xff0c;代表当前对象。 这里的this就是new出来的这个对象 this的本质: this是个引用在堆中指向它自己: this的细节: 访问成员方法: 访问构造器:...

vulnhub靶场之Deathnote

一.环境搭建 1.靶场描述 Level - easy Description : dont waste too much time thinking outside the box . It is a Straight forward box . This works better with VirtualBox rather than VMware 2.靶场下载 https://www.vulnhub.com/entry/deathnote-1,739/ 3.启动环…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...

6.计算机网络核心知识点精要手册

计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法&#xff1a;数据与控制信息的结构或格式&#xff0c;如同语言中的语法规则语义&#xff1a;控制信息的具体含义和响应方式&#xff0c;规定通信双方"说什么"同步&#xff1a;事件执行的顺序与时序…...

LeetCode 0386.字典序排数:细心总结条件

【LetMeFly】386.字典序排数&#xff1a;细心总结条件 力扣题目链接&#xff1a;https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n &#xff0c;按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...