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

【欧几里得算法以及扩展欧几里得算法】

news 来源：原创 2025/6/23 21:31:06

欧几里得算法

假设有两个非负整数 $a, b$ ,并且 $a, b$ 都不等于0，那么 $a, b$ 的最大公约数等于其中较小的数和 $a, b$ 相除的余数的最大公约数。

用公式表达为 $gcd(a,b)=gcd(b,a\pmod{b})$ ，其中 $a >= b$ 。

证明过程

$\begin{aligned} 假设 k 可以同时整除a,b。\\ &\because a>=b \\ &\therefore a=kb+r \\ &\therefore k \quad 也可以整除\quad r 。\\ &\therefore gcd(a,b)=gcd(b,a\pmod{b}) \quad 成立。 \end{aligned}$

代码实现

def gcd_by_euclidean_algorithm(a: int, b: int) -> int:while b != 0:a, b = b, a % breturn a# expect 1
print(gcd_by_euclidean_algorithm(3, 4))
# expect 4
print(gcd_by_euclidean_algorithm(12, 4))
# expect 6
print(gcd_by_euclidean_algorithm(18, 24))

扩展欧几里得算法

已知正整数 $a, b$ ，求解一组 $x, y$ ，使它们满足贝祖等式 $a x + b y = g c d (a, b)$ 。

特别的，当 $a\perp b$ 时，求解的 $x$ 为 $a$ 模 $b$ 的逆元，即 $ax\equiv 1\pmod{b}$ 。

扩展欧几里得算法的代码实现

扩展欧几里得算法实质上是求解贝祖等式的解。

def extended_gcd(a: int, b: int) -> int:# 当a为0时，贝祖等式的系数x=0,y=1,最大公约数为bif a == 0:return b, 0, 1# 递归求取最大公约数和贝祖系数d, x, y = extended_gcd(b % a, a)# 更新系数return d, y - (b // a) * x, x

根据扩展欧几里得算法求解模逆元

代码实现如下：

def mod_inverse(a, m):gcd, x, y = extended_gcd(a, m)# 当a,b不互质时，不存在模逆元if gcd != 1:raise Exception("Not found mod inverse.")return x % m

注意： 调用扩展欧几里得算法求得 $x$ 可能是负数，这时需要对 $x$ 模 $m$ ，确保 $x$ 是一个正数。

求证扩展欧几里得算法中系数公式

扩展欧几里得算法的核心是更新贝祖等式系数的公式，这些公式是基于欧几里得算法的递归性质推导出来的。下面是详细的证明过程：

初始等式: $a x + b y = g c d (a, b)$ ，其中 $x, y$ 是贝祖系数。

递归的第二层存在等式： $b\pmod{a} * x_1+a*y_1=gcd(b\pmod{a},a)$ 。

根据欧几里得算法可知： $gcd(a,b)=gcd(b\pmod{a},a)=d$ ，其中 $d$ 表示 $a, b$ 的最大公约数。

又因为： $\pmod{a} = b - \lfloor \frac{b}{a} \rfloor * a$
将此式子带入第二层的递归的等式中可得：

$(b-\lfloor \frac{b}{a} \rfloor *a)*x_1+a*y_1=d \\ a*(y_1-\lfloor \frac{b}{a} \rfloor *x_1) + b*x_1 = d$

因此递归时，两次递归之间的系数关系为：

$\begin{aligned} x&=y_1-\lfloor \frac{b}{a} \rfloor *x_1 \\ y&=x_1 \end{aligned}$

【欧几里得算法以及扩展欧几里得算法】

欧几里得算法假设有两个非负整数 a , b a,b a,b,并且 a , b a,b a,b都不等于0，那么 a , b a,b a,b的最大公约数等于其中较小的数和 a , b a,b a,b相除的余数的最大公约数。用公式表达为 g c d ( a , b ) g c d ( b , a ( m o d b ) ) gcd(a,b)gcd(b,a\pmod{b})…...

编程日记 2025/6/23 21:31:06

Gnome桌面右键弹出终端。 [rootlocalhost ~]# yum repolist 已加载插件：fastestmirror, langpacks /var/run/yum.pid 已被锁定，PID 为 2611 的另一个程序正在运行。 Another app is currently holding the yum lock; waiting for it to exit... [root…...

编程日记 2025/6/23 21:14:26

c#基于tcp的打印机共享程序可以打印图片

c sharp 基于tcp共享图片打印程序: 基于c#的tcp打印服务程序https://gitee.com/paoxi/tcpprint代码已经开源执行文件在下方 tcp打印发送端庖犠/c sharp 基于tcp共享图片打印程序 - Gitee.comhttps://gitee.com/paoxi/tcpprint/releases/tag/0.9...

编程日记 2025/5/29 13:06:41

二分查找算法

目录 1.二分查找 2.在排序数组中查找元素的第一个和最后一个位置 2.1题目解析 2.2算法原理 2.3编写代码 3.x的平方根 3.1题目解析 3.2算法原理 3.3编写代码 4.搜索插入位置 4.1题目解析 4.2算法原理 4.3编写代码 5.山脉数组的峰顶索引 5.1题目解析 5.2算法原理 …...

编程日记 2025/6/3 13:27:08

【Python技术】同花顺wencai涨停分析基础上增加连板分析

周末，有读者加我， 说之前的涨停分析是否可以增加连板分析。这个可以加上。先看效果这里附上完整代码： import streamlit as st import pywencai import pandas as pd from datetime import datetime, timedelta import plotly.graph_o…...

编程日记 2025/6/20 2:08:25

多线程的知识总结（8）：用 thread 类或全局 async (...) 函数，创建新线程时，谁才是在新线程里第一个被执行的函数

（40）用 thread 类或全局 async (…) 函数，创建新线程时，谁才是在新线程里第一个被执行的函数？ 弄清楚这个问题，有利于推测和理解线程中代码的执行流程。根据 thread 类和 async （…&#xff0…...

编程日记 2025/6/20 5:43:14

mp4影像和m4a音频无损合成视频方法

第一步：复制高清视频地址 url 第二步:打开网址粘贴复制的视频url视频下载第三步：下载-影像.mp4和-音频.m4a 第四步：合并视频； 使用ffmpeg进行无损合成（如果没有安装ffmpeg请自行下载安装下载 FFmpeg (p2hp.com)&…...

编程日记 2025/6/2 23:24:15

CEF 数据加密与网络安全

随着网络攻击的日益猖獗，确保应用的安全性已经成为开发者的首要任务。特别是在现代Web应用中，如何确保数据的加密存储、网络通信的安全性以及有效的认证机制成为至关重要的问题。对于基于 Chromium Embedded Framework (CEF) 的应用，开发者必…...

编程日记 2025/6/20 7:33:13

【Linux学习】十五、Linux/CentOS 7 用户和组管理

Linux下组和用户的管理都必须是root用户下进行： 一、组的管理 1.组的创建格式： groupadd 组名参数： -g：指定用户组的组ID（GID），如果不提供则由系统自动分配。【案例】创建一个名为 oldg…...

编程日记 2025/6/3 3:14:47

C语言实现图片文件的复制

在C语言中，直接处理图片文件（如JPEG、PNG等）的复制，通常涉及到文件I/O操作。这些图片文件是二进制文件，因此需要使用二进制模式读取和写入文件。图片文件复制代码： #include <stdio.h> #include&l…...

编程日记 2025/5/29 14:10:15

噪杂环境（房车改装市场）离线语音通断器模块

一直在坚持，却很难有机会上热门，在现在这个以流量为导向的时代，貌似很难靠所谓的坚守和热爱把产品成功的推向市场了。目前的客户仍然是以老客户为主，应用场景主要是房车改装，根据九客户的需求定制化一些模块。因为没有…...

编程日记 2025/6/4 15:40:09

网络安全知识点

第一章网络安全概述 1.2.1 网络安全概念P4 网络安全是指网络系统的硬件、软件及其系统中的数据受到保护，不因偶然的或恶意的原因而遭到破坏、更改、泄露，系统连续可靠正常地运行，网络服务不中断。 1.2.3 网络安全的种类P5 （1…...

编程日记 2025/6/3 13:16:29

QT＜32＞软件子页面最小化后再次点击置顶显示

一、前言在 Qt 中，当一个窗口被最小化后，再次点击恢复它时，默认情况下，窗口恢复的方式可能并不总是显示在最顶层。这通常是因为窗口恢复后会被置于操作系统的默认层次结构中，而不是直接处于最上层。为了确保恢复后的窗…...

编程日记 2025/6/22 20:23:52

TCP 数据传输的拆包和粘包了解吗？

前言： 上一篇我们了解了什么是 TCP 协议，以及 TCP 协议 3 次握手 4次挥手的原因，本篇来分享一下 TCP 数据的传输过程的拆包和粘包，以及 TCP 数据传输过程中的一些细节。计算机网络往期文章 TCP 为什么是 3 次握手 4 次挥手&am…...

编程日记 2025/6/21 9:26:14

Ubuntu常用自救方案

一、开机进入终端界面莫名其妙进入终端界面了且死活出不来，原因可能是下载了些不该下的，或者卸载了些不能卸的。万一真是这样可以尝试以下方法： 1.安装图形界面第一行必安，2、3没试过 sudo apt-get install ubuntu-desktop …...

编程日记 2025/6/20 8:19:13

决策曲线分析（DCA）中平均净阈值用于评价模型算法（R自定义函数）

决策曲线分析（DCA）中平均净阈值用于评价模型算法 DCA分析虽然不强调用来评价模型算法或者变量组合的优劣，但是实际应用过程中感觉DCA曲线的走势和模型的效能具有良好的一致性，其实这种一致性也可以找到内在的联系，比如…...

编程日记 2025/6/19 18:02:07

【小沐学GIS】基于C++绘制三维数字地球Earth（OpenGL、glfw、glut、QT）第三期

🍺三维数字地球系列相关文章如下🍺：1【小沐学GIS】基于C绘制三维数字地球Earth（456:OpenGL、glfw、glut）第一期2【小沐学GIS】基于C绘制三维数字地球Earth（456:OpenGL、glfw、glut）第二期3【小沐…...

编程日记 2025/6/20 1:58:12

回归预测 | MATLAB实现CNN-BiGRU-Attention卷积神经网络结合双向门控循环单元融合注意力机制多输入单输出回归预测

回归预测 | MATLAB实现CNN-BiGRU-Attention卷积神经网络结合双向门控循环单元融合注意力机制多输入单输出回归预测目录回归预测 | MATLAB实现CNN-BiGRU-Attention卷积神经网络结合双向门控循环单元融合注意力机制多输入单输出回归预测预测效果基本介绍程序设计参考资料预测效…...

编程日记 2025/6/1 18:20:12

深度解析相对路径、绝对路径与URL映射策略、MVC架构

一、相对路径与绝对路径的概念与应用路径管理是Web开发中的核心概念之一。理解不同类型的路径如何影响文件和资源的访问对于确保代码的灵活性、可维护性和可移植性至关重要。 1. 相对路径相对路径是指相对于当前文件或目录的位置来指定目标资源的路径。它不依赖于绝对的服…...

编程日记 2025/6/23 7:51:06

clipboard----封装复制组件

Clipboard.js 是一个轻量级的 JavaScript 库，旨在帮助开发者轻松地实现将文本复制到剪贴板的功能。它不依赖 Flash 或其他外部库，并且提供了一种简单的方式来响应用户的复制行为。Clipboard.js 支持绑定到任何元素（如按钮、图片等&#xff09…...

编程日记 2025/6/20 10:52:16

vue 中数据改变后，组件不更新

vue 中数据改变后，组件不更新 1.1. 确认响应式 1.2. 使用计算属性或侦听器 1.3. 检查异步更新队列 1.4. 手动触发更新 1.5. 检查数据绑定 1.6. 避免直接修改数组 1.7. 使用 Vue.set 或 this.$set 1.8. 检查作用域问题 1.9. 使用 Vue DevTools vue 中数据改变后&…...

编程日记 2025/6/20 15:46:03

使用C#和OPenCV实现圆形检测

文章目录霍夫变换使用 OpenCV 和 C# 实现圆形检测霍夫变换在计算机视觉中，圆形检测是一个常见且有用的任务，特别是在物体识别、图像分析和图形处理等领域。OpenCV 是一个强大的开源计算机视觉库，它提供了许多工具来实现不同的图像处理功能…...

编程日记 2025/6/20 9:05:27

C++ 给定字符串，然后给出开始要取的位置，返回取到的信息

3 happy new year 7 year 1 new 4 new year year error input #include <stdio.h> #include <string.h> void strmcpy(char* s, char* t, int m); int main() {int repeat, m;char t[1000], s[1000];scanf("%d", &repeat);getchar(); //吸收换行符in…...

编程日记 2025/6/2 5:59:00

异步持久化策略对比

1.背景游戏服务器其中一项重点工作，就是对游戏玩家的数据进行持久化，保证下次登录可以再续前缘。如果游戏服务器架构里没有缓存，每次操作都需要读写数据库，无疑对数据库带来非常大的压力。一旦使用缓存，就伴随异常持…...

编程日记 2025/6/2 9:15:34

手机租赁系统开发全流程解析与实用指南

内容概要在如今快速发展的科技时代，手机租赁系统已经成为一种新兴的商业模式，非常符合当下市场需求。那么，在开发这样一个系统的时候，首先要从需求分析和市场调研开始。在这一阶段，你需要了解用户需要什么&#xff0…...

编程日记 2025/6/20 16:09:56

apache-dubbo

dubbo 文档地址 dubbo 官方文档地址 https://dubbo.apache.org/zh-cn/docs/user/references/api.html nacos 官方文档地址 https://nacos.io/zh-cn/docs/quick-start.html nacos下载地址 https://github.com/alibaba/nacos/releases/download/2.3.0/nacos-server-2.3.0.…...

编程日记 2025/6/21 11:45:49

【JavaEE】网络（1）

🐵本篇文章开始讲解计算机网络相关的知识一、基础概念 1.1 局域网和广域网局域网→Local Area Network→简称LAN，局域网是局部组建的一种私有网络，局域网内的主机之间可以进行网络通信，局域网和局域网之间在没有连接的情况不能…...

编程日记 2025/6/20 1:46:50

系统思考—决策

今年在为不同公司交付培训与项目时，常常听到“降本增效”的提法，但关键是：“降”的到底是什么成本？裁员无疑是最快的成本削减方式，但也可能带来人心惶惶。人力是资本，不是成本。除非企业到了生死存亡的关头…...

编程日记 2025/6/22 11:29:12

nVisual 前端集成SDK使用说明

目前客户需要搭建自己的可视化产品,但需要使用nVisual的可视化视图功能,根据目前项目实施需求,决定做了一款简单版的SDK视图插件,这个小插件的主要功能是嵌入到客户项目里给客户提供 ‘详细视图’‘拓扑视图’或者是‘主视图’的展示功能.目前已经开发完毕,这里做一下简单介绍.…...

编程日记 2025/6/23 14:22:33

上传文件时获取音视频文件时长和文本文件字数

获取音视频文件时长和文本文件字数一、获取音视频文件时长二、计算文本文件字数最近有个需求，要求上传文件时获取音视频文件时长和文本文件字数🐶。发现这样的冷门资料不多，特做个记录。本文忽略文件上传功能，只封装核心的工具…...

编程日记 2025/6/22 11:54:27

[COLM 2024] V-STaR: Training Verifiers for Self-Taught Reasoners

本文是对 STaR 的改进方法，COLM 是 Conference On Language Models，大模型领域新出的会议，在国际上很知名，不过目前还没有被列入 ccf list（新会议一般不会列入）；作者来自高校、微软研究院和 Goo…...

编程日记 2025/6/21 21:22:43

【C++】string的主要功能模拟复现

经常调用的短小函数直接定义在头文件中，可以节省时间开销 #include<iostream> #include<assert.h> using namespace std; namespace mumu {class string{friend ostream& operator<<(ostream& _cout, const mumu::string& s);friend…...

编程日记 2025/6/23 12:15:00

Linux环境安装Jenkins

Linux环境安装Jenkins Jenkins和JDK的版本 Jenkins和JDK的版本需要对应，不然无法正常启动。 Jenkins稳定版下载地址 Jenkins服务手动使用命令启动和关闭Jenkins比较麻烦，所以可以把Jenkins设置成开机启动。创建Jenkins.sh文件 JAVA_HOME和jenk…...

编程日记 2025/6/20 20:10:10

Elasticsearch：ES|QL 中的全文搜索 - 8.17

细心的开发者如果已经阅读我前两天发布的文章 “Elastic 8.17：Elasticsearch logsdb 索引模式、Elastic Rerank 等”，你就会发现在 8.17 的发布版中，有一个重要的功能发布。那就是 ES|QL 开始支持全文搜索了。在今天的文章中我们来尝试一下。…...

编程日记 2025/6/21 1:40:59

Leetcode 3387. Maximize Amount After Two Days of Conversions

Leetcode 3387. Maximize Amount After Two Days of Conversions 1. 解题思路2. 代码实现题目链接：3387. Maximize Amount After Two Days of Conversions 1. 解题思路这一题思路上其实就是要分别求出day 1以及day 2中原始货币与其他各个货币之间的成交价&…...

编程日记 2025/6/21 17:45:45

Lumos学习王佩丰Excel第二十一讲：经典Excel动态图表实现原理

一、动态图表实现原理 1、理解图表中的数据系列在Excel图表中，系列指的是图表中的数据集合，它通常代表着一个数据源。每个系列都可以包含多个数据点，这些数据点在图表中以特定的形式展现，如柱状图中的柱子，折线图中…...

编程日记 2025/6/1 23:16:10

静态路由、RIP、OSPF、BGP的区别

静态路由：是管理员手动将路由写入到路由器中，配置简单开销小，但不能适应网络变化，只用于小型的网络 RIP，路由信息协议，属于距离矢量路由协议的一种，根据跳数来判断最优路由，如果跳数…...

编程日记 2025/6/23 1:30:51

解决 Flutter 在 Mac 上的编译错误

解决 Flutter 在 Mac 上的编译错误在使用 Flutter 进行项目开发并尝试在 Mac 设备上进行编译时，遇到了一系列的错误信息，这些错误信息给项目的构建与部署带来了阻碍。一、错误详情在编译过程中，Xcode 输出了大量的信息，其中…...

编程日记 2025/6/22 7:00:56

ECharts实现数据可视化入门详解

文章目录 ECharts实现数据可视化入门详解一、引言二、基础配置1.1、代码示例三、动态数据与交互2.1、代码示例四、高级用法1、多图表组合1.1、在同一容器中绘制多个图表1.2、创建多个容器并分别初始化 ECharts 实例1.3、实现多图联动五、总结 ECharts实现数据可视化入门详解…...

编程日记 2025/6/3 6:37:38

LRM-典型 Transformer 在视觉领域的应用,单个图像生成3D图像

https://yiconghong.me/LRM. 一、Abstract 第一个大型重建模型（LRM），它可以在5秒内从单个输入图像预测物体的3D模型。LRM采用了高度可扩展的基于transformer的架构，具有5亿个可学习参数，可以直接从输入图像中预测神经…...

编程日记 2025/6/20 2:00:48

Stream– ESP8266物联网应用，（客户端向服务器发送数据信息客户端向服务器请求数据信息）

Stream– ESP8266物联网应用 Stream对于ESP8266-Arduino语言来说指的是数据序列。请留意：在C编程中Stream常被翻译作“流”。我们认为将Stream称为数据序列更加直观。因为数据序列这一概念有两个很关键特点。第一个特点是“序”，即数据序列不能是杂乱…...

编程日记 2025/6/23 8:58:39

win10系统右下角没有显示网络图标 , 打开或关闭系统图标网络灰色

win10系统右下角没有显示网络图标 / 打开或关闭系统图标网络灰色 win10系统右下角没有显示网络图标, 并且打开或关闭系统图标网络灰色解决方案: 首先，按【Ctrl Alt Del】组合键，然后点击【任务管理器】。任务管理器窗口，找到并选择【Wind…...

编程日记 2025/6/1 9:00:37

Python使用Selenium库获取网页节点元素、名称、内容的方法

我们要用到一些网页源码信息，例如获取一些节点的class内容， 除了使用Beautifulsoup来解析，还可以直接用Selenium库打印节点（元素）名称，用来获取元素的文本内容或者标签名。例如获取下面的class的内容&am…...

编程日记 2025/6/3 6:32:24

onnx文件转pytorch pt模型文件

onnx文件转pytorch pt模型文件 1.onnx2torch转换及测试2.存在问题参考文献从pytorch格式转onnx格式，官方有成熟的API；那么假如只有onnx格式的模型文件，该怎样转回pytorch格式？ https://github.com/ENOT-AutoDL/onnx2torch提供了…...

编程日记 2025/6/21 2:16:12

计算机网络中的SIP协议是什么？

SIP（Session Initiation Protocol，会话初始化协议）是由IETF（Internet Engineering Task Force，因特网工程任务组）制定的多媒体通信协议。以下是对SIP的详细简述： 一、SIP的基本概念 SIP是一个…...

编程日记 2025/6/21 10:27:48

Apache Kylin最简单的解析、了解

官网：Overview | Apache Kylin 一、Apache Kylin是什么？ 由中国团队研发具有浓厚的中国韵味，使用神兽麒麟（kylin）为名的一个OLAP多维数据分析引擎:（据官方给出的数据） 亚秒级响应&#xff…...

编程日记 2025/6/22 11:07:28

axfbinhexelf文件区别

0 Preface/Foreword axf,bin,hex,elf四个都能存在于嵌入式软件领域。 1 文件介绍嵌入式软件中常见的文件包含： axf，包含调试信息，文件最大。调试信息放在机器码前面。elfhex，包含地址信息，文件内容较大。bin&#x…...

编程日记 2025/6/1 16:06:24

MySQL表自增id溢出的故障复盘，你是如何解决与监控的

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons：JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram，自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 ？ 5 IDEA必装的插件&…...

编程日记 2025/5/30 19:30:34

03、SpirngMVC核心（下）

一、关于RESTful编程风格什么是RESTful RESTful的英文全称是：Representational State Transfer（表述性状态转移） RESTful是Web服务接口的一种设计风格。它定了一组约束和规范，可以让Web服务接口更加简洁、易于理解、易于扩展、安全可靠。 RESTful对于请求的约束如下：…...

编程日记 2025/6/23 19:52:56

【游戏设计原理】10 - 科斯特的游戏理论

科斯特的游戏理论强调了游戏与学习之间的关系，认为“玩得开心”与“学习”是紧密相连的。换句话说，游戏的核心魅力在于通过适当的挑战和不断的学习进程激发玩家的内啡肽循环，这让玩家在不断的探索和进步中找到乐趣。科斯特的理论通过游戏是…...

编程日记 2025/6/22 1:19:18