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

欧几里得算法(简单理解版,非严格证明)

        欧几里得算法用于求解两个整数的最大公约数,又称为辗转相除

        依据的基本定理:

                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><!--头部开始&#xff08;h…...

鸿蒙APP之从开发到发布的一点心得

引言&#xff1a; 做鸿蒙开发大概有1年左右时间了&#xff0c;从最开始的看官方文档、看B站视频&#xff0c;到后来成功发布两款个人APP&#xff08;房贷计算极简版、时简时钟 轻喷&#xff0c;谢谢&#xff09;。简单描述一下里边遇到的坑以及一些经历吧。 学习鸿蒙开发 个…...

某小程序sign签名参数逆向分析

文章目录 1. 写在前面2. 接口分析3. 分析还原 【&#x1f3e0;作者主页】&#xff1a;吴秋霖 【&#x1f4bc;作者介绍】&#xff1a;擅长爬虫与JS加密逆向分析&#xff01;Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python…...

智能风控/数据分析 聚合 分组 连接

data。head&#xff08;&#xff09;查看前几行 data.head() 是一个在Python的Pandas库中常用的方法&#xff0c;用于查看DataFrame对象的前几行数据。默认情况下&#xff0c;head() 方法会返回DataFrame的前5行数据&#xff0c;但是你也可以通过传递一个整数参数来指定返回的…...

Unity3D PBR光照计算公式推导详解

前言 在Unity3D中&#xff0c;PBR&#xff08;Physically Based Rendering&#xff0c;基于物理的渲染&#xff09;光照模型是一种高级光照模型&#xff0c;它模拟了真实世界中光的传播和反射过程&#xff0c;从而提供了更加逼真的渲染效果。PBR光照模型的计算公式涉及多个物理…...

行为树详解(6)——黑板模式

【动作节点数据共享】 行为树中需要的参数可以来自游戏中的各个模块&#xff0c;如果仅需从多个模块获取少量参数&#xff0c;那么可以直接在代码中调用其他模块的单例继而层层调用获取数据。 如果获取的参数量很大&#xff0c;从架构上看&#xff0c;我们需要通过加一个中间…...

Vue.js与其他框架有哪些兼容性?

Vue.js的兼容性主要体现在几个方面&#xff0c;包括浏览器支持、运行环境适应性、与其他库和框架的集成能力等。以下是更详细的解释&#xff1a; 浏览器兼容性 现代浏览器&#xff1a;Vue.js广泛支持所有主流的现代浏览器&#xff0c;如Google Chrome, Firefox, Safari, Edge…...

Java 8 Stream 介绍

Java 8 Stream 介绍 1. 什么是Stream&#xff1f; Stream&#xff08;流&#xff09;是Java 8引入的全新概念&#xff0c;它是一个支持串行和并行聚合操作的元素序列。Stream API提供了一种声明式的方式来处理数据集合&#xff0c;可以让我们以一种类似SQL查询的方式处理数据…...

Java NIO、AIO分析

好的&#xff0c;下面将对Java中的**NIO&#xff08;Non-blocking IO&#xff09;和AIO&#xff08;Asynchronous IO&#xff09;**进行更深入的分析&#xff0c;重点探讨它们的特点和具体的应用场景。 一、Java NIO&#xff08;Non-blocking IO&#xff09;深入分析 1. 主要…...

pip下载包出现SSLError

报错&#xff1a; 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…...

零成本的互联网创业创意有哪些?

在互联网时代&#xff0c;创业的门槛大大降低&#xff0c;即使没有大量的资金投入&#xff0c;也有许多机会可以实现创业梦想。以下将为您介绍一些零成本的互联网创业创意&#xff0c;帮助您在互联网的海洋中找到属于自己的宝藏。 一、内容创作与自媒体 &#xff08;一&#…...

linux ubantu重启桌面

在 Ubuntu 系统中&#xff0c;重启桌面环境通常有几种方法&#xff0c;具体取决于你所使用的桌面环境&#xff08;如 GNOME、KDE 等&#xff09;。下面是几种常用的重启桌面的方法&#xff1a; 重启 GNOME 桌面环境 如果你使用的是 GNOME 桌面环境&#xff08;Ubuntu 默认桌面…...

DeepSeek重新定义“Open“AI

“面对颠覆性技术&#xff0c;闭源所创造的护城河是暂时的。即使是OpenAI的闭源方法也无法阻止他人赶超。” ——梁文锋&#xff0c;DeepSeek CEO DeepSeek V3 是一个拥有6710亿参数的开源AI模型&#xff0c;正在提升AI效率的新标准。它在相对有限的预算下进行训练&#xff0c…...

iOS - 自旋锁

在 Objective-C 运行时中大量使用自旋锁&#xff0c;主要有以下几个原因&#xff1a; 1. 性能考虑 上下文切换成本 // 自旋锁实现 static ALWAYS_INLINE void OSSpinLockLock(volatile OSSpinLock *lock) {do {while (lock->value ! 0) {__asm__ volatile ("pause&q…...

web应用网站如何启用http2请求

要启用 HTTP/2 协议&#xff0c;您需要确保您的 Web 服务器软件支持 HTTP/2&#xff0c;并进行相应的配置。以下是一些常见的 Web 服务器软件及其启用 HTTP/2 的方法&#xff1a; 1. Nginx 对于 Nginx&#xff0c;您需要确保使用的是 1.9.5 或更高版本&#xff0c;因为这些版本…...

python进阶06:MySQL

课后大总结 Day1 一、数据库命令总结 1.连接数据库 连接数据库进入mysql安装目录打开bin文件夹&#xff0c;输入cmd(此命令后无分号)mysql.exe -u root -ppassword命令后输入密码:root 设置密码set passwordpassword("root123"); 查看所有数据库show databases; …...

mac 使用zip2john破解zip压缩包密码

一、下载&#xff1a; git clone https://github.com/magnumripper/JohnTheRipper.git cd JohnTheRipper/src ./configure sudo make -s clean && sudo make -sj4 cd ../run二、使用&#xff1a; zip2john提取提取 ZIP 文件的哈希&#xff1a; ./zip2john protecte…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...