欧几里得算法(简单理解版,非严格证明)
欧几里得算法用于求解两个整数的最大公约数,又称为辗转相除
依据的基本定理:
GCD(a,b)=GCD(a%b,b)
证明:
对于搞理论的人可能需要会严格证明,但是对于我们一般人而言,只要能理解其原理并记住即可,后者实际上是非常简单的,且看:
如果我们有两个数a, b,假设其最大公约数m
那么有a%m==0,b%m==0
那么我们是不是可以将a看成k*b+c,那么(k*b+c)%m=(k*b)%m+c%m=0+c%m,容易发现m也正是b与c的最大公约数,
所以求a与b的最大公约数,也就是求c=a%b与b的最大公约数,于是基本定理就是这么来的:
- GCD(a,b)=GCD(a%b,b)
那么这样辗转相除下去,最后一定会得到0,
如果a是b的最大公约数m非1,那么得到(0,m),最大公约数就是m
如果不是,那么最后a%b一定得1,即(1,b),然后b%1==0,最后得(0,1),最大公约数就是1
这里需要注意参数顺序, 要么:
GCD(a,b)=GCD(b,a%b)
GCD(a,b)=GCD(b%a,b)
不能写成GCD(a,b)=GCD(a%b,b),这样会死递归
那么代码就可以写了:
int GCD(int a,int b)
{return a?GCD(b%a,a):b;
}
相关文章:
欧几里得算法(简单理解版,非严格证明)
欧几里得算法用于求解两个整数的最大公约数,又称为辗转相除 依据的基本定理: GCD(a,b)GCD(a%b,b) 证明: 对于搞理论的人可能需要会严格证明,但是对于我们一般人而言,只要能理解其原理并记住即可,后者实际上…...
Mac软件介绍之录屏软件Filmage Screen
软件介绍 Filmage Screen 是一款专业的视频录制和编辑软件,适用于 Mac 系统 可以选择4k 60fps,可以选择录制电脑屏幕,摄像头录制,可以选择区域录制。同时也支持,简单的视频剪辑。 可以同时录制电脑麦克风声音 标准…...
Ubuntu cuda-cudnn中断安装如何卸载
文章目录 问题描述解决方法使用强制移除 问题描述 Ubuntu22.04系统,在终端中执行apt insatll安装或dpkg .deb安装时如果强制关闭终端会导致安装失败(安装包会变成iu状态或ru状态,安装成功的应该是ii状态) 此时,无论是…...
CSS——7.CSS注释
<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>css注释</title><link rel"stylesheet" type"text/css" href"a.css"/></head><body><!--头部开始(h…...
鸿蒙APP之从开发到发布的一点心得
引言: 做鸿蒙开发大概有1年左右时间了,从最开始的看官方文档、看B站视频,到后来成功发布两款个人APP(房贷计算极简版、时简时钟 轻喷,谢谢)。简单描述一下里边遇到的坑以及一些经历吧。 学习鸿蒙开发 个…...
某小程序sign签名参数逆向分析
文章目录 1. 写在前面2. 接口分析3. 分析还原 【🏠作者主页】:吴秋霖 【💼作者介绍】:擅长爬虫与JS加密逆向分析!Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python…...
智能风控/数据分析 聚合 分组 连接
data。head()查看前几行 data.head() 是一个在Python的Pandas库中常用的方法,用于查看DataFrame对象的前几行数据。默认情况下,head() 方法会返回DataFrame的前5行数据,但是你也可以通过传递一个整数参数来指定返回的…...
Unity3D PBR光照计算公式推导详解
前言 在Unity3D中,PBR(Physically Based Rendering,基于物理的渲染)光照模型是一种高级光照模型,它模拟了真实世界中光的传播和反射过程,从而提供了更加逼真的渲染效果。PBR光照模型的计算公式涉及多个物理…...
行为树详解(6)——黑板模式
【动作节点数据共享】 行为树中需要的参数可以来自游戏中的各个模块,如果仅需从多个模块获取少量参数,那么可以直接在代码中调用其他模块的单例继而层层调用获取数据。 如果获取的参数量很大,从架构上看,我们需要通过加一个中间…...
Vue.js与其他框架有哪些兼容性?
Vue.js的兼容性主要体现在几个方面,包括浏览器支持、运行环境适应性、与其他库和框架的集成能力等。以下是更详细的解释: 浏览器兼容性 现代浏览器:Vue.js广泛支持所有主流的现代浏览器,如Google Chrome, Firefox, Safari, Edge…...
Java 8 Stream 介绍
Java 8 Stream 介绍 1. 什么是Stream? Stream(流)是Java 8引入的全新概念,它是一个支持串行和并行聚合操作的元素序列。Stream API提供了一种声明式的方式来处理数据集合,可以让我们以一种类似SQL查询的方式处理数据…...
Java NIO、AIO分析
好的,下面将对Java中的**NIO(Non-blocking IO)和AIO(Asynchronous IO)**进行更深入的分析,重点探讨它们的特点和具体的应用场景。 一、Java NIO(Non-blocking IO)深入分析 1. 主要…...
pip下载包出现SSLError
报错: ERROR: Could not install packages due to an OSError: HTTPSConnectionPool(host‘files.pythonhosted.org’, port443): Max retries exceeded with url: /packages/8a/c2/ae7227e4b089c6a8210920db9d5ac59186b0a84eb1e6d96b9218916cdaf1/taming_transform…...
零成本的互联网创业创意有哪些?
在互联网时代,创业的门槛大大降低,即使没有大量的资金投入,也有许多机会可以实现创业梦想。以下将为您介绍一些零成本的互联网创业创意,帮助您在互联网的海洋中找到属于自己的宝藏。 一、内容创作与自媒体 (一&#…...
linux ubantu重启桌面
在 Ubuntu 系统中,重启桌面环境通常有几种方法,具体取决于你所使用的桌面环境(如 GNOME、KDE 等)。下面是几种常用的重启桌面的方法: 重启 GNOME 桌面环境 如果你使用的是 GNOME 桌面环境(Ubuntu 默认桌面…...
DeepSeek重新定义“Open“AI
“面对颠覆性技术,闭源所创造的护城河是暂时的。即使是OpenAI的闭源方法也无法阻止他人赶超。” ——梁文锋,DeepSeek CEO DeepSeek V3 是一个拥有6710亿参数的开源AI模型,正在提升AI效率的新标准。它在相对有限的预算下进行训练,…...
iOS - 自旋锁
在 Objective-C 运行时中大量使用自旋锁,主要有以下几个原因: 1. 性能考虑 上下文切换成本 // 自旋锁实现 static ALWAYS_INLINE void OSSpinLockLock(volatile OSSpinLock *lock) {do {while (lock->value ! 0) {__asm__ volatile ("pause&q…...
web应用网站如何启用http2请求
要启用 HTTP/2 协议,您需要确保您的 Web 服务器软件支持 HTTP/2,并进行相应的配置。以下是一些常见的 Web 服务器软件及其启用 HTTP/2 的方法: 1. Nginx 对于 Nginx,您需要确保使用的是 1.9.5 或更高版本,因为这些版本…...
python进阶06:MySQL
课后大总结 Day1 一、数据库命令总结 1.连接数据库 连接数据库进入mysql安装目录打开bin文件夹,输入cmd(此命令后无分号)mysql.exe -u root -ppassword命令后输入密码:root 设置密码set passwordpassword("root123"); 查看所有数据库show databases; …...
mac 使用zip2john破解zip压缩包密码
一、下载: git clone https://github.com/magnumripper/JohnTheRipper.git cd JohnTheRipper/src ./configure sudo make -s clean && sudo make -sj4 cd ../run二、使用: zip2john提取提取 ZIP 文件的哈希: ./zip2john protecte…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
