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

记录：扩展欧几里得算法

news 来源：原创 2025/7/18 6:46:43

本文遵循 CC BY-NC-ND 4.0 协议，作者： $\texttt{U•ェ•*U}$ ，转载请获得作者授权。

前置知识

裴蜀定理/贝祖定理：若 $a, b$ 是整数，且 $\gcd(a,b)=d$ ，那么对于任意整数 $x, y$ ， $a\times x + b\times y = k$ 中的 $k$ 一定是 $d$ 的倍数。（特别地，如果 $a, b$ 是整数，那么一定存在整数 $x, y$ 使得 $a\times x + b\times y = \gcd(a,b)$ ）

引入

引入扩展欧几里得算法，可用于求解以下几种问题：

给定两个非零的整数 $a$ 和 $b$ ，求一组整数解 $(x, y)$ 使得 $a\times x + b\times y = \gcd(a,b)$ 成立，其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。
逆元

从欧几里得算法推导：
$\gcd(x, y) \to \gcd(y, x \mod y) \\ \Downarrow \\ \forall x_{n} = 1, y_{n} = 0 \\ \\ \forall a\times x_1 + b \times x_1 = \gcd \\ \Downarrow \\ \forall b\times x_2 + (a\mod b)\times y_2 = \gcd \\ \forall a\times x_1 + b \times x_1 = b\times x_2 + (a\mod b)\times y_2 \\ \forall a\times x_1 + b \times y_1 = a\times y_1 + b\times (x_2\times \frac{a}{b}\times y_2)$

于是反推出原来的值（ $x_1, y_1$ ）：

void exgcd(int a, int b, int &x, int &y) {if (a % b == 0) x = 0, y = 1;else {exgcd(b, a % b, y, x);y -= a / b * x;}
}

证明：
[TODO]

求同余式

对两个整数 $a, b$ ，如果它们除以 $d$ 的余数相同，则称它们模 $d$ 同余，记作 $a\equiv b (\mod d)$ 。

在同余号两侧同时加、减、乘任意整数，同余式仍成立。

我们设一个同余式 $ax\equiv c (\mod m)$ ，那么可以分讨求解：

若 $c\mod \gcd(a,m) \neq 0$ ，则同余方程 $ax\equiv c(\mod\ m)$ 无解。
若 $c\mod \gcd(a, m) = 0$ ，则同余方程的解为 $x’ = x + \frac{\gcd(a, m)}{m}\times \mathbb{N} $。

求逆元

对任意给定的 $x$ 和 $p$ ，显然 $\times x ^ {-1} \equiv 1 (\mod p)$ 。可以利用
这个式子计算 $x ^ {-1}$ 。

其中 $x$ 和 $p$ 是已知量，所以上式是一个不定方程， $x ^ {−1}$ 和 $k$
是变量。用 $\texttt{exgcd}$ 求解可以得到 $x ^ {−1}$ 。

$\texttt{C++}$ 代码（线性求逆元）：

int n, p, inv[3000010];
signed main() {cin >> n >> p;inv[1] = 1;cout << 1 << endl;for (int i = 2; i <= n; i ++) {inv[i] = (int)(p - p / i) * inv[p % i] % p;printf("%lld\n", inv[i]);}return 0;
}

相关文章：

记录：扩展欧几里得算法

本文遵循 CC BY-NC-ND 4.0 协议，作者： U•ェ•*U \texttt{U•ェ•*U} U•ェ•*U，转载请获得作者授权。前置知识裴蜀定理/贝祖定理：若 a , b a,b a,b 是整数，且 gcd ⁡ ( a , b ) d \gcd(a,b)d gcd(a,b)d&#xf…...

编程日记 2025/7/18 6:46:43

学习笔记——《Java面向对象程序设计》-抽象和接口

参考教材： Java面向对象程序设计（第3版）微课视频版清华大学出版社抽象方法抽象方法是使用abstract关键字修饰的成员方法，抽象方法在定义时不需要实现方法体。抽象方法的定义格式如下： abstract void 方法名称…...

编程日记 2025/7/16 5:04:19

MySQL中根据binlog日志进行恢复

MySQL中根据binlog日志进行恢复排查 MySQL 的 binlog 日志问题及根据 binlog 日志进行恢复的方法一、引言二、排查 MySQL 的 binlog 日志问题（一）确认 binlog 是否开启（二）查找 binlog 文件位置和文件名模式（三&#…...

编程日记 2025/7/13 19:12:57

数据库sql语句中 GROUP BY 关键字详解及字段要求

GROUP BY 关键字详解及字段要求 GROUP BY 的核心作用将查询结果按指定字段分组，常与聚合函数（如 COUNT, SUM, AVG 等）结合使用，对分组后的数据进行统计计算。 GROUP BY 后字段的要求非聚合字段必须出现在 GROUP BY 子句中&…...

编程日记 2025/7/15 21:58:11

数据集 | 柑橘果目标检测数据集

文章目录一、数据集概述1.1 数据标注实例1.2 数据集技术规格二、样本类别详解2.1 树上柑橘样本2.2 树下柑橘样本三、标注工具四、数据下载地址一、数据集概述在农业智能化领域，柑橘果园的自动化监测与管理一直面临着几个关键挑战： 果实定位准确性…...

编程日记 2025/7/14 5:11:09

Arduino示例代码讲解：Project 11 - Crystal Ball 水晶球

Arduino示例代码讲解：Project 11 - Crystal Ball 水晶球 Project 11 - Crystal Ball 水晶球程序功能概述功能：硬件要求：输出：代码结构全局变量`setup()` 函数`loop()` 函数读取倾斜开关状态：检测状态变化：保存状态：运行过程注意事项Project 11 - Crystal Ball 水晶球 /…...

编程日记 2025/7/13 18:05:37

Redis—为何持久化使用子进程

AOF重写以及bgsave的时候为什么采用fork子进程而不是子线程？ 进程间内存隔离独立的内存空间：子进程拥有与主进程独立的内存空间，确保即使在重写过程中发生崩溃或错误，也不会影响主进程的运行和内存状态。数据安全性&#xff…...

编程日记 2025/7/13 21:25:46

Vue3 + Vite + TS,使用 ExcelJS导出excel文档，生成水印，添加背景水印，dom转图片，插入图片，全部代码

Vue3 Vite TS,使用 ExcelJS导出excel文档，生成水印，添加背景水印，dom转图片，插入图片，全部代码 ExcelJS生成文档并导出导出表头其他函数生成水印设置文档的背景水印dom 转图片插入图片全部代码 ExcelJS 读取&#…...

编程日记 2025/7/14 12:51:05

VulnHub-DarkHole_1靶机渗透教程

VulnHub-DarkHole_1靶机渗透教程 1.靶机部署 [Onepanda] Mik1ysomething 靶机下载：https://download.vulnhub.com/darkhole/DarkHole.zip 直接使用VMware打开就行导入成功，打开虚拟机，到此虚拟机部署完成！ 注意&#xff1a…...

编程日记 2025/7/14 1:54:52

Python设计模式：对象池

1. 什么是对象池设计模式？ 对象池设计模式是一种创建型设计模式，主要用于管理和复用对象，以提高性能和资源利用率。它通过维护一个对象的集合（池），来避免频繁地创建和销毁对象，从而减少内存分配…...

编程日记 2025/6/29 10:16:30

【上海大学数据库原理实验报告】MySQL数据库的C/S模式部署

实验目的掌握Linux环境下MySQL数据库的安装、初始化和基本配置。通过配置MySQL的网络通信，熟悉数据库的远程访问机制及其安全性要求。实验内容在腾讯云上租借两台服务器，打开3306端口以允许MySQL远程访问。图 1 租到的服务器可在控制台观察其状态…...

编程日记 2025/6/29 9:33:32

deepseek快速生成简历

目录一、需求二、模板例子三、生成简历四、其他说明一、需求现在我准备跳槽到一家公司，这家公司已经发布了招聘需求，现在你想跳槽到这家公司，我们可以利用deepseek快速生成符合这家公司的简历内容。二、模板我们要进行指令明确的结构…...

编程日记 2025/7/16 10:42:32

什么是机器视觉3D无序堆叠抓取

机器视觉3D无序堆叠抓取是一种结合三维视觉感知、人工智能算法和机器人控制的技术，旨在从杂乱无序堆叠的物体中识别、定位并抓取目标物体。该技术广泛应用于工业自动化（如物流分拣、装配制造）、仓储管理、食品加工等领域，解决了传统二维视觉或固定规则堆叠场景下的抓取难题…...

编程日记 2025/6/29 11:51:47

Shell脚本中的字符串截取和规则变化

文章目录前言if通配符判断if判断多个条件规则变化字符串的两个示例改变中间段数字改变末尾段数字总结前言科技的发展会带来习惯的改变，特别是对于我们这批敲代码的，之前还积累一些奇巧淫技，想着在必要的时候卖弄一下，自从生成…...

编程日记 2025/7/18 1:29:47

云账号安全事件应急响应指南：应对来自中国IP的异常访问

在当今数字化时代，云服务已成为企业IT基础设施的核心。然而，随之而来的安全挑战也日益突出。本文将详细介绍当发现云账号被来自中国的IP地址异常利用时，应如何快速有效地响应，以确保账户安全并最小化潜在风险。 1. 确认异常活动首先，我们需要确认是否真的发生了安全事件…...

编程日记 2025/7/14 13:27:38

python番外

#作者：允砸儿 #日期：乙巳青蛇年三月廿五在开始数据库的分享之前笔者简单写以下关于python的番外。笔者这块可能写的不是很好csdn上面有很多大佬，笔者仅以自己的思维和想法与大家分享以下。安装必看笔者在这里贴一个网址https://www.…...

编程日记 2025/7/14 10:16:18

Jetson Orin NX 16G 配置GO1强化学习运行环境

这一次收到了Jrtson Orin NX, 可以进行部署了。上一次在nano上的失败经验 Jetson nano配置Docker和torch运行环境_jetson docker-CSDN博客本次的目的是配置cuda-torch-python38环境离机运行策略。 Jetson Orin NX SUPER 1. 烧录镜像参考链接在ubuntu系统中安装sdk manag…...

编程日记 2025/7/14 23:51:10

Embedding与向量数据库__0422

thinking：做一个项目 1，业务背景，价值 2，方法，工具 3，实践（现有的代码，改写的代码） cursor编程有个cursor settings ->privacy mode隐私模式，但是只要连上…...

编程日记 2025/6/29 9:53:22

正向代理和反向代理

正向代理和反向代理是两种在不同场景下使用的代理技术，它们有以下区别： 目标和作用正向代理目标 ：主要是为客户端服务，帮助客户端去访问外部网络资源。例如，企业内部网络中的员工可能需要访问互联网，但直…...

编程日记 2025/6/29 9:45:12

Android JNI开发中头文件引入的常见问题与解决方案，提示：file not found

Android JNI开发中头文件引入的常见问题与解决方案问题场景（新手易犯错误） 假设你在开发一个JNI项目，想要实现一个线程安全的队列（SafeQueue），于是直接在cpp目录下创建了safe_queue.h文件，并开…...

编程日记 2025/6/29 12:29:23

三网通电玩城平台系统结构与源码工程详解（二）：Node.js 服务端核心逻辑实现

本篇文章将聚焦服务端游戏逻辑实现，以 Node.js Socket.io 作为主要通信与逻辑处理框架，展开用户登录验证、房间分配、子游戏调度与事件广播机制的剖析，并附上多个核心代码段。一、服务端文件结构概览 /server/├── index.js …...

编程日记 2025/7/16 23:59:02

案例：Windows 作为客户端免密验证（公钥验证）

一、实验前提 1.服务器端为 Linux 系统，且能够正常运行相关命令和服务，如 systemctl、ssh 服务等。同时，客户端为 Windows 系统，且具备使用 SSH 客户端工具连接到 Linux 服务器的条件 2.Linux 服务器上已安装并配置好 SSH 服务&…...

编程日记 2025/6/29 10:53:55

leetcode 二分查找

704. Binary Search 代码： class Solution { public:int search(vector<int>& nums, int target) {int n nums.size();int left 0;int right n-1;int res -1;while(left < right){int mid (leftright)/2;if(nums[mid] target){res mid;break;}…...

编程日记 2025/6/29 11:37:09

C++：STL模板

STL模板分为函数模板和类模板。我想交换两个数字，但是类型不同，例如我想交换整形a,b，和double类型的d1,d2。如果使用C语言来实现，那么需要像下面一样写两个swap函数，但是除了类型不同，其它都一样&#xf…...

编程日记 2025/6/29 11:52:27

NumPy入门：从数组基础到数学运算

目录一、NumPy 数组基础 （一）创建数组 （二）数组索引 （三）数组切片二、数组操作 （一）形状操作 （二）数组合并与分割三、基本数学运算 （…...

编程日记 2025/6/29 11:42:23

文档管理 Document Management

以下是关于项目管理中文档管理的深度解析，结合高项（如软考高级信息系统项目管理师）教材内容，系统阐述文档管理的理论框架、核心流程及实战应用：一、文档管理的基本概念 1. 定义文档管理是对项目全生命周期中产生的各类文档进行规范化管理的过程，包括创建、存储、版…...

编程日记 2025/7/15 8:50:52

TCP三次握手与四次挥手面试回答版本

面试官：说一下TCP三次握手的过程参考面试回答： 在第一次握手的时候、客户端会随机生成初始化序号、放到TCP报文头部的序号字段中、同时把SYN标志设置为1 这样就表示SYN报文（这里是请求报文）。客户端将报文放入 TCP 报文首部的序…...

编程日记 2025/7/17 11:11:34

Windows7升级Windows10，无法在此驱动器上安装Windows

一、现象描述台式机工作站，从Windows7升级Windows10，采用MediaCreationTool_22H2制作U盘启动盘，安装系统遇到问题如下： 二、原因分析是由于硬盘格式不是GPT硬盘，而Windows系统只能安装到GPT硬盘上，所以…...

编程日记 2025/7/16 19:07:17

【阿里云大模型高级工程师ACP习题集】2.2 扩展答疑机器人的知识范围

练习题【单选题】在RAG应用的建立索引过程中，文本向量化的主要目的是（）。 A. 将文本转换为计算机能理解的数字形式，便于比较相似度 B. 对文本进行分类 C. 去除文本中的噪声数据 D. 提取文本中的关键词【多选题】以下属于RAG应用中建立索引步骤的有（）。 A. 文档解析 B…...

编程日记 2025/6/29 12:23:20

Mininet--node.py源码解析

算法逻辑详解 1. 核心类结构代码通过面向对象的方式定义了网络模拟中的各类节点，继承关系如下： Node ├── Host │ └── CPULimitedHost ├── Switch │ ├── UserSwitch │ ├── OVSSwitch │ ├── OVSBridge │ └── IVSS…...

编程日记 2025/7/16 9:58:23

龙虎榜——20250422

指数目前还是震荡为主，等待后续的选择方向 2025年4月22日龙虎榜行业方向分析一、核心主线方向化工（新材料产能优化） • 代表标的：红宝丽（环氧丙烷/锂电材料）、亚太实业（农药中间体&#xff…...

编程日记 2025/7/15 1:38:03

掌握 Altium Designer：轻松定制“交换器件”工具栏

在PCB设计过程中，快速交换器件（如电阻、电容、IC等）是提高效率的关键。Altium Designer提供了灵活的工具栏定制功能，让用户可以创建专属的"交换器件"工具栏，将常用操作集中管理，减少菜单切换时间…...

编程日记 2025/7/17 1:38:16

npm的基本使用安装所有包，安装删除指定版本的包，配置命名别名

npm的基本使用安装所有包，安装删除指定版本的包，配置命名别名安装所有依赖指定版本安装/删除包给 npm 脚本配置“命令别名（自定义命令）” ✅ 一、安装所有包（恢复依赖） 如果项目中已经存在 package.json…...

编程日记 2025/7/16 11:25:33

transformer预测寿命

完整的Transformer剩余寿命预测代码体系。该代码已在锂电池和工业设备数据集验证，支持端到端训练和预测。 python import torch import numpy as np from torch import nn, optim from sklearn.preprocessing import MinMaxScaler from torch.utils.data import Da…...

编程日记 2025/7/15 23:01:05

如何将视频轻松转换为GIF动态图

在社交媒体和日常聊天中，GIF动态图因其体积小、循环播放的特点而广受欢迎。很多人希望将视频中的精彩片段制作成GIF图分享给朋友或用于内容创作。本文将详细介绍如何简单快速地将视频转换为GIF动态图，无需复杂软件，几步即可完成。转换步骤 …...

编程日记 2025/7/10 4:22:48

一文详解Pytorch环境搭建：Mac电脑pip安装Pytorch开发环境

对于希望在本地环境中进行深度学习开发的开发者来说，配置PyTorch工具是至关重要的一步。。对于Mac用户而言，搭建PyTorch开发环境并不复杂，本文将详细介绍如何在Mac电脑上使用pip安装PyTorch开发环境，帮助开发者快速上手深度学习开…...

编程日记 2025/7/17 4:35:41

ios开发中xxx.debug.dylib not found

问题描述：error: Build input file cannot be found: /Users/zhoutao/Library/Developer/Xcode/DerivedData/XfLive-effvxneriinvzwexohdsevonmhsk/Build/Products/Debug-iphoneos/xFLive.app/xFLive.debug,dylib’, pid you forget to declare this file as an out…...

编程日记 2025/7/15 4:47:41

Linux嵌入式系统SQlite3数据库学习笔记

前言 SQlite3是一个轻量级、嵌入式的关系型数据库管理系统，其中具有的核心特点： 1：嵌入式数据库：无需独立服务器进程，数据库直接嵌入到应用程序中。 2：单文件存储：整个数据库存储为单个文件&…...

编程日记 2025/7/17 21:19:16

【教程】安装 iterm2 打造漂亮且高性能的 mac 终端

【教程】安装 iterm2 打造漂亮且高性能的 mac 终端_mac 安装iterm2-CSDN博客安装myzh 参考文章：https://blog.csdn.net/qq_44741467/article/details/135727124 下载地址：GitCode - 全球开发者的开源社区,开源代码托管平台 1、下载到本地 2、进入下载的…...

编程日记 2025/7/16 19:39:27

C++IO流

CIO流 IO: 向设备输入数据和输出数据 C的IO流设备: 文件、控制台、特定的数据类型(stringstream) c中,必须通过特定的已经定义好的类, 来处理IO(输入输出) 读写文件：文件流文件流: 对文件进行读写操作头文件: <fstream> 类库: ifstream 对文件输入&am…...

编程日记 2025/7/17 1:38:29

Swoole-添加自定义路由实现控制器访问

swoole本身不支持路由功能，默认情况我们实现路由访问可能要这样 $path $request->server[request_uri]switch ($path){case /favicon.ico:$response->status(404);$response->end(Not Found);break;case /abc/def/gg:$response->end("/abc/def/gg…...

编程日记 2025/7/15 23:19:09

Win10 关闭自动更新、关闭自动更新并重启

Windows 专业版及企业版用户可以通过组策略禁用或延迟更新。操作步骤如下： 按 Win R，输入 gpedit.msc 打开组策略编辑器。导航到：计算机配置 > 管理模板 > Windows 组件 > Windows 更新。修改以下设置： • 配置自…...

编程日记 2025/7/14 21:34:39

鸿道Intewell操作系统助力工业机器人控制系统自主可控

工业机器人与人形机器人的爆发式增长，正成为东土科技鸿道Intewell系统实现跨越式发展的核心引擎。从技术适配到生态重构，东土科技的三大核心能力与两大机器人赛道形成深度共振，其市场空间和产业地位将迎来指数级跃升。一、工业机器人&…...

编程日记 2025/6/29 11:13:47

第十一届机械工程、材料和自动化技术国际会议（MMEAT 2025）

重要信息官网：www.mmeat.net 时间：2025年06月23-25日地点：中国-深圳部分展示征稿主题智能制造和工业自动化复合材料与高性能材料先进制造技术自动化机器人系统云制造与物联网集成精密制造技术智能生产线优化实时数据分析与过…...

编程日记 2025/7/16 4:37:35

go语言八股文

1.go语言的接口是怎么实现接口（interface）是一种类型，它定义了一组方法的集合。任何类型只要实现了接口中定义的所有方法，就被认为实现了该接口。代码的实现 package mainimport "fmt"// 定义接口 type Shape inte…...

编程日记 2025/7/16 18:34:34

短视频广告创意策划简历模板

模板信息简历范文名称：短视频广告创意策划简历模板，所属行业：其他 | 职位，模板编号：A4I63M 专业的个人简历模板，逻辑清晰，排版简洁美观，让你的个人简历显得更专业，找到…...

编程日记 2025/6/29 10:26:46

2.Spring MVC与WebFlux响应式编程

目录一、Spring MVC核心机制与工作原理 • 请求处理流程：DispatcherServlet分发机制、HandlerMapping与HandlerAdapter • 核心组件：ViewResolver、ModelAndView、拦截器（Interceptor） • 注解驱动开发：Controller、…...

编程日记 2025/7/15 8:50:27

【重走C++学习之路】16、AVL树

目录一、概念二、AVL树的模拟实现 2.1 AVL树节点定义 2.2 AVL树的基本结构 2.3 AVL树的插入 1. 插入步骤 2. 调节平衡因子 3. 旋转处理 4. 开始插入 2.4 AVL树的查找 2.5 AVL树的删除 1. 删除步骤 2. 调节平衡因子 3. 旋转处理 4. 开始删除结语一、概念 …...

编程日记 2025/7/16 9:12:44

蓝桥杯 19.合根植物

合根植物原题目链接题目描述 W 星球的一个种植园被分成 m n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的…...

编程日记 2025/6/29 11:44:50

爆改 toxml 组件支持数据双向绑定解决数据刷新问题

GGGGGGGGGGGGGGGGGithub地址自行研究 sbfkcel/towxml: 微信小程序HTML、Markdown渲染库https://github.com/sbfkcel/towxml原组件是以导入数据渲染信息为目的、本文以AI数据返回小程序为模拟效果演示默认情况只在ready 环节进行渲染静态资源 1、对传入数据容器的位置做处理 …...

编程日记 2025/7/17 8:03:32