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

【算法】欧几里得与拓展欧几里得算法

news 来源：原创 2025/7/20 6:07:35

一、欧几里得算法

二、拓展欧几里得算法

2.1 裴蜀定理

2.2 拓展欧几里得算法

2.3 例题

三、线性同余方程

3.1 概念

3.2 例题

一、欧几里得算法

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

其思路：

gcd(a, b) = gcd(b, a%b)，其中gcd(a, b)代表a和b的最大公约数
当b=0时，a为最大公约数

例如要求36和24的最大公约数即gcd(36, 24)，可转而求gcd(24, 36%24)即gcd(24, 12)，再转为求gcd(12, 0），此时最大公约数即为12

其代码实现：

int gcd(int a, int b)
{if(b == 0)return a;return gcd(b, a % b);
}

二、拓展欧几里得算法

2.1 裴蜀定理

若a，b是整数，且d = gcd(a, b)，则对于任意的整数x和y，总有ax+by是d的倍数
对于给定的整数x和y，方程ax+by=c有整数解(x, y)的充分必要条件是c是gcd(a, b)的倍数

2.2 拓展欧几里得算法

由裴蜀定理，我们知道对于给定的整数a和b，方程ax + by = gcd(a, b)总有整数解(x, y)

那么，如何求出这个整数解(x, y)？

由欧几里得算法可得gcd(a, b) = gcd(b, a%b)
由裴蜀定理，bx' + (a%b)y' = gcd(b, a%b)
由1和2，得bx' + (a%b)y' = gcd(a, b) 即 ax + by = bx' + (a%b)y'
由a%b = a - b*(a/b)【注意这里的a/b是向下取整】，得ax + by = bx' + [a - b*(a/b)]y'
上式整理得a(x-y') - b[x' - y - (a/b)y'] = 0，即x-y'=0、x' - y - (a/b)y'=0
得x = y'，y = x'-(a/b)y'

得到求解后，我们就可以通过递归不断传入x和y来计算整数解(x, y)了。拓展欧几里得的递归终点和欧几里得的终点类似，当b为0时即ax+by = a时返回{x=1,y=0}的解，并通过上一次的结果向下更新

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

int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}

2.3 例题

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;int n, a, b, x, y;int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}void solve()
{cin >> n;for(int i = 0;i < n; i++){cin >> a >> b;exgcd(a, b, x, y);cout << x << " " << y << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

三、线性同余方程

3.1 概念

线性同余方程ax ≡ b(mod m)，要求我们求出一个整数x，使得a和x的乘积模上m等于b

对于这个方程，可以用拓展欧几里得算法求解：

ax ≡ b(mod m)可转化为对于整数x，存在整数y使得ax = my + b
令y' = -y，则上式转化为ax + my' = b
用拓展欧几里得算法求ax' + my' = gcd(a, m)
只要b是gcd(a, m)的倍数则说明方程成立，整数x存在，x = x' * (b / gcd(a, m))

3.2 例题

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;int n, a, b, m, x, y;int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}void solve()
{cin >> n;for(int i = 0;i < n; i++){cin >> a >> b >> m;int gcd = exgcd(a, m, x, y);if(b % gcd == 0) //b是gcd倍数：成立cout << x * (b / gcd) % m << endl; //为什么要%m？因为可以保证x在int范围内且同余belse //b不是gcd倍数：无解cout << "impossible" << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

完.

【算法】欧几里得与拓展欧几里得算法

目录一、欧几里得算法二、拓展欧几里得算法 2.1 裴蜀定理 2.2 拓展欧几里得算法 2.3 例题三、线性同余方程 3.1 概念 3.2 例题一、欧几里得算法欧几里得算法又称辗转相除法，可用于求解两个数的最大公约数其思路： gcd(a, b) gcd(b, a%b…...

编程日记 2025/7/20 6:07:35

组合数的求法

1.如果是多组查询的话，需要用数组去储存阶乘的值 n!/(m!(n-m)!) P4071 [SDOI2016] 排列计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<cstdio> #include<iostream> #include<map> #include<cstring> #include<cmath&g…...

编程日记 2025/7/19 14:59:28

【环境搭建】更新Docker Compose到v2.x版本以支持--profile选项

Docker版本陈旧也是搭建的环境起不来的一个重要原因，比如 --profile 选项是 Docker 20.10.0 版本及以上版本才开始支持的，在 Docker Compose v2.1（及以上版本）中引入用于对服务进行分组和按需启动。更新 Docker Compose 到 v2.x…...

编程日记 2025/7/20 1:33:05

解决 java -jar 报错：xxx.jar 中没有主清单属性

问题复现在使用 java -jar xxx.jar 命令运行 Java 应用程序时，遇到了以下错误： xxx.jar 中没有主清单属性这个错误表示 JAR 文件缺少必要的启动信息，Java 虚拟机无法找到应用程序的入口点。本文将介绍该错误的原因以及如何通过修改 pom.xm…...

编程日记 2025/7/20 5:19:59

AIGC-----AIGC在虚拟现实中的应用前景

AIGC在虚拟现实中的应用前景引言随着人工智能生成内容（AIGC）的快速发展，虚拟现实（VR）技术的应用也迎来了新的契机。AIGC与VR的结合为创造沉浸式体验带来了全新的可能性，这种组合不仅极大地降低了VR内容的…...

编程日记 2025/7/19 22:39:29

【博主推荐】C#的winfrom应用中datagridview常见问题及解决方案汇总

文章目录 1.datagridview绘制出现鼠标悬浮数据变空白2.datagridview在每列前动态添加序号2.1 加载数据集完成后绘制序号2.2 RowPostPaint事件绘制 3.datagridview改变行样式4.datagridview后台修改指定列数据5.datagridview固定某个列宽6.datagridview某个列的显示隐藏7.datagr…...

编程日记 2025/7/20 5:37:35

Selenium 自动化测试demo

场景描述： 模拟用户登录页面操作，包括输入用户名、密码、验证码。验证码为算数运算，如下： 使用到的工具和依赖： 1. Selenium：pip install selenium 2. 需要安装浏览器驱动：这里使用的是Edge 3…...

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

深度神经网络模型压缩学习笔记二：离线量化算法和工具、实现原理和细节

文章目录一、离线量化基础概念二、离线量化难点三、离线量化算法介绍四、离线量化工具介绍五、离线量化工具整体设计结构六、离线量化工具代码解读七、实践：Dipoorlet量化MobileNet 一、离线量化基础概念二、离线量化难点三、离线量化算法介绍四、离线量化工…...

编程日记 2025/7/20 5:45:19

uni-app运行安卓模拟器 MuMu模拟器

最近公司开发移动端系统，使用真机时每次调试的时候换来换去的麻烦，所以使用模拟器来调试方便。记录一下安装和连接的过程一、安装MuMu模拟器百度搜索MuMu模拟器并打开官网或者点这里MuMu模拟器官网点击下载模拟器安装模拟器，如果系统…...

编程日记 2025/7/19 21:36:36

网络安全，文明上网（6）网安相关法律

列举 1. 《中华人民共和国网络安全法》： - 这是中国网络安全的基本法律，于2017年6月1日开始实施。该法律明确了网络运营者的安全保护义务，包括采取数据分类、重要数据备份和加密等措施。 2. 《中华人民共和国数据安全法》： …...

编程日记 2025/7/19 19:15:45

Perforce Automation With Python

11/2024 出版 MP4 |视频：h264， 19201080 |音频：AAC，44.1 KHz 语言：英语 |大小： 2.65 GB |时长： 5 小时 18 分钟使用 Python 脚本简化与 Perforce 版本控制系统相关的生产流程您将学到什么 …...

编程日记 2025/7/20 5:17:46

卷积神经网络学习记录

目录神经网络基础定义： 基本组成部分工作流程卷积层（卷积定义）【CONV】： 卷积层（Convolutional Layer） 特征提取：卷积层的主要作用是通过卷积核（或滤波器）运算提…...

编程日记 2025/7/20 5:56:31

Spring Cloud Alibaba

What is SCA Spring Cloud Alibaba致力于提供微服务开发的一站式解决方案。此项目包含开发分布式应用服务的必需组件，方便开发者通过Spring Cloud编程模型轻松使用这些组件来开发分布式应用服务。依托Spring Cloud Alibaba，您只需要添加一些注解和少量…...

编程日记 2025/7/20 5:37:34

【AI绘画】Midjourney进阶：色调详解（上）

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: AI绘画 | Midjourney 文章目录 💯前言💯Midjourney中的色彩控制为什么要控制色彩？为什么要在Midjourney中控制色彩？ 💯色调白色调淡色调明色调 &#x1f4af…...

编程日记 2025/7/20 5:52:33

文章目录找到字符串中所有字母异位词 class Solution { public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int sLen s.size(), pLen p.size(), validChar;// 母串长度比子串长度还小直接返回空vectorif (sLen < pLen)return ret;// …...

编程日记 2025/7/19 14:28:02

C++：final 关键字用于阻止类被继承或阻止虚函数被进一步重写

final 关键字的作用 C11 引入了 final 关键字，用于阻止类被继承或阻止虚函数被进一步重写。防止类被继承：在类声明后添加 final，表示该类不能被继承。防止虚函数被重写：在虚函数声明后添加 final，表示该虚函数在派生…...

编程日记 2025/7/20 5:40:13

sql漏洞

目录 SQL漏洞产生的原因未对用户输入进行验证和过滤： 动态SQL语句的拼接： 不安全的数据库配置： 缺乏安全意识和培训： 使用过时的技术或框架： 如何避免SQL漏洞产生使用参数化查询： 对用户输入进行…...

编程日记 2025/7/20 5:40:13

SQL 复杂查询

目录复杂查询一、目的和要求二、实验内容 （1）查询出所有水果产品的类别及详情。查询出编号为“00000001”的消费者用户的姓名及其所下订单。（分别采用子查询和连接方式实现） 查询出每个订单的消费者姓名及联系方式。在…...

编程日记 2025/7/20 5:30:42

在 PyTorch 训练中使用 `tqdm` 显示进度条

在 PyTorch 训练中使用 tqdm 显示进度条在深度学习的训练过程中，实时查看训练进度是非常重要的，它可以帮助我们更好地理解训练的效率，并及时调整模型或优化参数。使用 tqdm 库来为训练过程添加进度条是一个非常有效的方式，本文将…...

编程日记 2025/7/20 5:33:14

PYNQ 框架 - 时钟系统 + pl_clk 时钟输出不准确问题

目录 1. 简介 2. PS 时钟计算 2.1 计算框架 2.2 KV260 的参考时钟 2.3 PL_CLK 设置 3. 测试 3.1 Block design 3.2 引脚绑定 3.3 使用 AD2 测量 3.4 调整分频 4. PYNQ 时钟驱动 4.1 源码解析 4.2 查看 PL_CLK 4.3 配置 PL_CLK 5. 总结 1. 简介 ZYNQ MPSoC 具有…...

编程日记 2025/7/20 5:24:06

【Reinforcement Learning】强化学习下的多级反馈队列（MFQ）算法

📢本篇文章是博主强化学习（RL）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅…...

编程日记 2025/7/20 5:25:24

Cocos编辑器

1、下载下载地址：https://www.cocos.com/creator-download 2、编辑器界面介绍官方链接：https://docs.cocos.com/creator/3.8/manual/zh/editor/ 3、项目结构官方链接：https://docs.cocos.com/creator/3.8/manual/zh/getting-started/…...

编程日记 2025/7/20 5:31:55

Linux kernel 堆溢出利用方法（三）

前言本文我们通过我们的老朋友heap_bof来讲解Linux kernel中任意地址申请的其中一种比赛比较常用的利用手法modprobe_path（虽然在高版本内核已经不可用了但ctf比赛还是比较常用的）。在通过两道道近期比赛的赛题来讲解。 Arbitrary Address Allocation…...

编程日记 2025/7/20 5:55:12

文心一言与千帆大模型平台的区别：探索百度AI生态的双子星

随着人工智能技术的迅猛发展，越来越多的公司开始投入资源开发自己的AI解决方案。在中国，百度作为互联网巨头之一，不仅在搜索引擎领域占据重要位置，还在AI领域取得了显著成就。其中，“文心一言”和“千帆大模型平台”便…...

编程日记 2025/7/20 6:05:11

JavaWeb——SpringBoot原理

10.1. 配置优先级 10.1.1. 配置文件 properties > yml(推荐) > yaml 10.1.2. Java系统属性、命令行参数命令行参数 > Java系统属性 > 配置文件 10.2. Bean管理 10.2.1. 手动获取bean ApplicationContext，IOC容器对象 10.2.2. bean作用域 10.2.3.…...

编程日记 2025/7/18 10:31:25

【算法】连通块问题（C/C++）

目录连通块问题解决思路步骤： 初始化： DFS函数： 复杂度分析代码实现（C） 题目链接：2060. 奶牛选美 - AcWing题库解题思路： AC代码： 题目链接：687. 扫雷 -…...

编程日记 2025/7/15 4:11:43

Oracle RAC 环境下数据文件误建在本地目录的处理过程

问题描述在 Oracle RAC 环境中，有时会误将数据文件创建在本地目录，导致其他节点无法访问该数据文件，从而报出 ORA-01157 和 ORA-01110 错误。问题分析错误日志 Mon Nov 16 19:02:38 2021 Errors in file /u01/app/oracle/diag/rdbms/orc…...

编程日记 2025/7/12 7:18:26

使用R语言绘制简单地图的教程

今天主要讲的部分是绘制静态地图，使用的R语言绘图包是tmap，关于介绍就不多讲，下面开始代码的讲解，小白也可以放心食用。 1、绘制简单的单幅地图，这里以新西兰地区为例 #导入必要的包 library(tmap) library(sp) libr…...

编程日记 2025/7/14 19:19:24

【人工智能】基于PyTorch的深度强化学习入门：从DQN到PPO的实现与解析

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！深度强化学习（Deep Reinforcement Learning）是一种结合深度学习和强化学习的技术，适用于解决复杂的决策问题。深度Q网络（DQN）和近端策略优化（PPO）是其中两种经典的算法，被广泛应用于游戏、机器人控…...

编程日记 2025/7/15 1:22:22

学习threejs，使用设置lightMap光照贴图创建阴影效果

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：threejs gis工程师文章目录一、🍀前言1.1 ☘️THREE.MeshLambertMaterial…...

编程日记 2025/7/16 19:52:08

类和对象（中）

文章目录目录1. 类的6个默认成员函数2. 构造函数3. 析构函数4. 拷贝构造函数5. 赋值运算符重载5.1 运算符重载5.2 赋值运算符重载5.3 日期类实现 6. const成员函数7. 取地址及const取地址操作符重载目录类的6个默认成员函数构造函数析构函数拷贝构造函数赋值运算符重载cons…...

编程日记 2025/7/19 21:35:55

编程之路，从0开始：预处理详解（完结篇）

Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！ 我的博客：<但凡. 我的专栏：编程之路这一篇预处理详解是我们C语言基础内容学习的最后一篇，也是我们的专栏&#xff…...

编程日记 2025/7/15 12:51:46

[chrome]黑色界面插件，PDF合并插件

Dark Reader_chrome插件下载,最新浏览器扩展,crx离线安装包 - 插件小屋合并 PDF_chrome插件下载,最新浏览器扩展,crx离线安装包 - 插件小屋下载的zip包解压成crx，然后把后缀名改为rar，然后解压，再导入解压的目录。...

编程日记 2025/7/2 4:15:28

【c语言】文件操作详解 - 从打开到关闭

文章目录 1. 为什么使用文件？2. 什么是文件？3. 如何标识文件？4. 二进制文件和文本文件？5. 文件的打开和关闭5.1 流和标准流5.1.1 流5.1.2 标准流 5.2 文件指针5.3 文件的打开和关闭 6. 文件的读写顺序6.1 顺序读写函数6.2 对比一组…...

编程日记 2025/7/17 10:32:45

AIGC--AIGC与人机协作:新的创作模式

AIGC与人机协作：新的创作模式引言人工智能生成内容（AIGC）正在以惊人的速度渗透到创作的各个领域。从生成文本、音乐、到图像和视频，AIGC使得创作过程变得更加快捷和高效。然而，AIGC并非完全取代了人类的创作角色&am…...

编程日记 2025/7/10 1:25:17

刷题日常（数据流中的中位数，逆波兰表达式求值，最长连续序列，字母异位词分组）

数据流中的中位数描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()…...

编程日记 2025/7/15 20:38:15

Redis突然变慢，有哪些原因？

目录一、存在bigkey 二、如果Redis 实例设置了内存上限 maxmemory，有可能导致 Redis 变慢三、开启了内存大页四、使用了Swap 五、网络带宽过载六、频繁短连接一、存在bigkey 如果Redis实例中存储了 bigkey，那么在淘汰删除 bigkey 释放内存时&…...

编程日记 2025/7/19 17:02:50

Qt入门1——认识Qt的几个常用头文件和常用函数

1.头文件 ① #include <QPushButton>——“按钮”头文件； ② #include <QLabel>——“标签”头文件； ③ #include <QFont>——“字体”头文件； ④#include <QDebug>——输出相关信息； 2. 常用函数/类的基…...

编程日记 2025/7/15 22:57:17

Banana Pi BPI-CanMV-K230D-Zero 采用嘉楠科技 K230D RISC-V芯片设计

概述 Banana Pi BPI-CanMV-K230D-Zero 采用嘉楠科技 K230D RISC-V芯片设计,探索 RISC-V Vector1.0 的前沿技术，选择嘉楠科技的 Canmv K230D Zero 开发板。这款创新的开发板是由嘉楠科技与香蕉派开源社区联合设计研发，搭载了先进的勘智 K230D 芯片。 K230…...

编程日记 2025/7/19 21:35:55

CSS笔记（一）炉石传说卡牌设计1

目标我要通过html实现一张炉石传说的卡牌设计问题其中必须就要考虑到各个元素的摆放，形状的调整来达到满意的效果。通过这个联系来熟悉一下CSS的基本操作。 1️⃣ 基本概念在CSS里面有行元素，块元素，内联元素，常见的行元…...

编程日记 2025/7/16 4:56:45

怎么在宿主机上通过ssh连接虚拟机 VirtualBox 中的linux系统

通过 Xshell 连接 VirtualBox 中的 linux 虚拟机，您需要确保以下几个步骤都正确配置： 1. 配置 VirtualBox 网络您需要将 VirtualBox 虚拟机的网络适配器设置为支持 SSH 连接的模式： 打开 VirtualBox，选择您的 Ubuntu 虚拟机&am…...

编程日记 2025/7/13 23:47:27

Spire.PDF for .NET【页面设置】演示：打开 PDF 时自动显示书签或缩略图

用户打开 PDF 文档时，他们会看到 PDF 的初始视图。默认情况下，打开 PDF 时不会显示书签面板或缩略图面板。在本文中，我们将演示如何设置文档属性，以便每次启动文件时都会打开书签面板或缩略图面板。 Spire.PDF for .NET 是一款独…...

编程日记 2025/7/15 14:44:59

241125学习日志——[CSDIY] [InternStudio] 大模型训练营 [17]

CSDIY：这是一个非科班学生的努力之路，从今天开始这个系列会长期更新，（最好做到日更），我会慢慢把自己目前对CS的努力逐一上传，帮助那些和我一样有着梦想的玩家取得胜利！！&…...

编程日记 2025/7/19 22:31:19

Centos 7 安装 Docker 最新版本

文章目录一、卸载旧版本二、安装最新版本docker三、问题解决3.1 启动docker报错3.2 启动容器报错一、卸载旧版本 #如果之前安装过旧版本的Docker，可以使用下面命令卸载 yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest …...

编程日记 2025/7/15 21:18:04

JavaScript的基础数据类型

一、JavaScript中的数组定义数组是一种特殊的对象，用于存储多个值。在JavaScript中，数组可以包含不同的数据类型，如数字、字符串、对象、甚至其他数组。数组的创建有两种常见方式： 字面量表示法：let fruits [apple…...

编程日记 2025/7/15 9:03:39

网络安全-------防止被抓包

1.Ios应用网络安全之https 安全套接字层 (Secure Socket Layer, SSL) 是用来实现互联网安全通信的最普遍的标准。Web 应用程序使用 HTTPS（基于 SSL 的 HTTP），HTTPS 使用数字证书来确保在服务器和客户端之间进行安全、加密的通信。在 SSL 连接…...

编程日记 2025/7/18 16:24:37