算法——数论——GCD和LCM

目录

GCD(最大公约数)

 1、欧几里得算法

LCM(最小公倍数)

一、试题 算法训练 抗击虫群


GCD(最大公约数)

  • 整数 a 和 b 的最大公约数是指能同时整除 a 和 b 的最大整数,记为 gcd(a,b)
  • -a的因子和a的因子相同,例如gcd(15,18) = gcd(-15,-18) = 3
  • 性质:
  • 裴蜀定理:

 1、欧几里得算法

  • 用辗转相除法求GCD,即 gcd(a,b)=gcd(b,a mod b)
  • 代码逻辑:
    • 如果 a 能够整除 b,那么 b 就是 a 和 b 的最大公约数;
    • 否则,最大公约数即为 b 和 a 除以 b 的余数的最大公约数。
    • 我们重复使用这个逻辑,将原先的 b 替换为余数,并将原先的余数替换为新的 b,直到余数变为 0。此时,b 就是最大公约数。

  • 另外还有两种算法:更相减损术和Stein算法,用得较少
public static int gcd(int a,int b){return b!=0 ? gcd(b , a % b) : a;
}

LCM(最小公倍数)

  •  a 和 b 的最小公倍数表示为 lcm(a,b)
  • 推论:gcd(a,b) * lcm(a,b) = ab(具体过程略,该公式为结论,说明了LCM和GCD之间的关系)
public static int lcm(int a,int b){return a / gcd(a , b) * b;//如果先作乘法可能会溢出
}

一、试题 算法训练 抗击虫群

 分析:

  • 每次都是加 p 的药物量,不能多不能少,(n+m)% p == 0,而且刚好加满两个容器
  • 要快,即是 p 的数值要尽可能大,但最后一勺 p 不能超出容器
  • 综上,求 n 和 m 的最大公约数,使用欧几里得算法
  • 建议先去系统、完整地学习一下这个知识点,再回来处理题目
package no1_1;
import java.util.*;class Main {public static void main(String[] args){Scanner sc=new Scanner(System.in);while(sc.hasNextLine()) {int n = sc.nextInt();int m = sc.nextInt();sc.nextLine();//换行int p=gcd(n,m);System.out.println(p);}}public static int gcd(int a,int b) {//欧几里得算法计算最大公约数return b!=0?gcd(b,a%b):a;}
}

 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

C# 字体大小的相关问题

设置字体大小无法这么写, button1.Font.Size 20; 这个是只读属性; 把字体大小改为16, button2.Font new Font(button2.Font.Name, 16); 程序运行的时候先看一下窗体和控件的默认字体尺寸,都是9;然后点b…

v-if 和v-show 的区别

第074个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 提供vue2的一些基本操作:安装、引用,模板使用,computed&a…

【大厂AI课学习笔记】【1.5 AI技术领域】(7)图像分割

今天学习到了图像分割。 这是我学习笔记的脑图。 图像分割,Image Segmentation,就是将数字图像分割为若干个图像子区域(像素的集合,也被称为超像素),改变图像的表达方式,以更容易理解和分析。 …

春晚刘谦第二个魔术原理讲解

目录 1. 先说一下步骤:2. 原理讲解:2.1 第一步分析2.1 第二步分析2.1 第三步分析2.1 第四步分析2.1 第五步分析2.1 第六步分析2.1 第七步分析2.1 第八步分析2.1 第七步重新分析 小结: 首先,先叠个甲。我本人很喜欢刘谦老师&#x…

大水仙花数求解

输入位数,求解水仙花数。暴力求解,位数如果太多,会超时。 思路: (1)11333355和33331155看上去是不一样的两个数,但是它们又一样,因为相同数字出现的次数一样。 (2&…

大模型学习 一

https://www.bilibili.com/video/BV1Kz4y1x7AK/?spm_id_from333.337.search-card.all.click GPU 计算单元多 并行计算能力强 指数更重要 A100 80G V100 A100 海外 100元/时 单卡 多卡并行: 单机多卡 模型并行 有资源的浪费 反向传播 反向传播(B…

《MySQL 简易速速上手小册》第6章:MySQL 复制和分布式数据库(2024 最新版)

文章目录 6.1 设置和管理复制6.1.1 基础知识6.1.2 重点案例:使用 Python 设置 MySQL 主从复制6.1.3 拓展案例 1:自动故障转移6.1.4 拓展案例 2:设置双主复制 6.2 复制的类型和策略6.2.1 基础知识6.2.2 重点案例:使用 Python 设置半…

Kafka 入门介绍

目录 一. 前言 二. 使用场景 三. 分布式的流平台 四. Kafka 的基本术语 4.1. 主题和日志 (Topic 和 Log) 4.2. 分布式(Distribution) 4.3. 异地数据同步技术(Geo-Replication) 4.4. 生产者&#xf…

SpringBoot源码解读与原理分析(二十)IOC容器的刷新(一)

文章目录 7 IOC容器的刷新7.1 初始化前的预处理7.1.1 初始化属性配置7.1.2 初始化早期事件的集合 7.2 初始化BeanFactory7.2.1 注解驱动的refreshBeanFactory7.2.2 XML驱动的refreshBeanFactory7.2.3 获取BeanFactory 7.3 BeanFactory的预处理配置7.3.1 ApplicationContextAwar…

Spring基础 - Spring简单例子引入Spring要点

Spring基础 - Spring简单例子引入Spring要点 设计一个Spring的Hello World 设计一个查询用户的案例的两个需求&#xff0c;来看Spring框架帮我们简化了什么开发工作 pom依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"htt…

FastJson、Jackson使用AOP切面进行日志打印异常

FastJson、Jackson使用AOP切面进行日志打印异常 一、概述 1、问题详情 使用FastJson、Jackson进行日志打印时分别包如下错误&#xff1a; 源码&#xff1a; //fastjon log.info("\nRequest Info :{} \n"&#xff0c; JSON.toJSONString(requestInfo)); //jackson …

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

题目描述 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 题目示例 输入&#xff1a;inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出&a…

【正式】今年第一篇CSDN(纯技术教学)

一、文件上传简介 文件上传漏洞是指用户上传了一个可执行的脚本文件&#xff08;木马、病毒、恶意脚本、webshell等&#xff09;&#xff0c;并通过此脚本文件获得了执行服务器端命令的能力。上传点一般出现在头像、导入数据、上传压缩包等地方&#xff0c;由于程序对用户上传…

《Git 简易速速上手小册》第10章:未来趋势与扩展阅读(2024 最新版)

文章目录 10.1 Git 与开源社区10.1.1 基础知识讲解10.1.2 重点案例&#xff1a;Python 社区使用 Git10.1.3 拓展案例 1&#xff1a;Git 在大型开源项目中的角色10.1.4 拓展案例 2&#xff1a;支持开源项目的 Git 托管平台 10.2 新兴技术与 Git 的整合10.2.1 基础知识讲解10.2.2…

《剑指Offer》笔记题解思路技巧优化 Java版本——新版leetcode_Part_1

《剑指Offer》笔记&题解&思路&技巧&优化_Part_1 &#x1f60d;&#x1f60d;&#x1f60d; 相知&#x1f64c;&#x1f64c;&#x1f64c; 相识&#x1f622;&#x1f622;&#x1f622; 开始刷题1. LCR 120. 寻找文件副本——数组中重复元素2. LCR 121. 寻找目…

Amazon Dynamo学习总结

目录 一、Amazon Dynamo的问世 二、Amazon Dynamo主要技术概要 三、数据划分算法 四、数据复制 五、版本控制 六、故障处理 七、成员和故障检测 一、Amazon Dynamo的问世 Amazon Dynamo是由亚马逊在2007年开发的一种高度可扩展和分布式的键值存储系统&#xff0c;旨在解…

Android13多媒体框架概览

Android13多媒体框架概览 Android 多媒体框架 Android 多媒体框架旨在为 Java 服务提供可靠的接口。它是一个系统&#xff0c;包括多媒体应用程序、框架、OpenCore 引擎、音频/视频/输入的硬件设备&#xff0c;输出设备以及一些核心动态库&#xff0c;比如 libmedia、libmedi…

ARM PAC/BTI/MTE三剑客精讲与实战

一、PAC指针认证精讲与实战 思考 1、什么是栈溢出攻击&#xff1f;什么是代码重用攻击&#xff1f;区别与联系&#xff1f; 2、栈溢出攻击的软&硬件缓解技术有哪些&#xff1f;在TF-A&OPTEE上的应用&#xff1f; 3、什么是ROP攻击&#xff1f;对ROP攻击的缓解技术&…

Redis -- 数据库管理

目录 前言 切换数据库(select) 数据库中key的数量&#xff08;dbsize&#xff09; 清除数据库&#xff08;flushall flushdb&#xff09; 前言 MySQL有一个很重要的概念&#xff0c;那就是数据库database&#xff0c;一个MySQL里面有很多个database&#xff0c;一个datab…

龙芯开启ssh服务——使用Putty连接

本文采用龙芯3A6000处理器&#xff0c;Loongnix操作系统。 为了能使用其他电脑远程操控龙芯电脑&#xff0c;需要打开loongnix的ssh服务&#xff0c;并在其他电脑里使用putty连接loongnix。 1 修改ssh配置文件 命令行输入&#xff1a; sudo vim /etc/ssh/sshd_config按下i插…