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

【蓝桥杯】Python算法——求逆元的两种算法

news 来源：原创 2025/8/5 5:29:21

零、前言

距离25年蓝桥杯还有大概三个月时间，接下来重点应该会放在蓝桥杯备考方向，一起努力，一起加油

一、逆元

什么是逆元？这是数论中的一个基本概念。如果存在 $ax\equiv1(mod \ n)$ 则 $x$ 为 $a$ 在模 $n$ 意义下的逆元。可以简单地理解为，求一个 $x$ 使得 $ax\ mod\ n=1$
逆元的意义在哪呢？如果遇到需要求 $a/b\ mod\ n$ 的情况，则可以转化为分子a乘以分母b的逆元的形式，这样我们将除法转化为乘法，提高了计算效率。

二、扩展欧几里得算法

那么怎么求解逆元呢？由前面给出的公式 $ax\equiv1(mod \ n)$ ，不难看出求逆元 $x$ 就是求解等式的解： $a x + n y = 1$ 因为 $(ax+ny)\ mod\ n = ax\ mod\ n$ ,求出了 $x$ 和 $y$ ，那么 $x$ 就是 $a$ 的逆元。
为了方便推导，我们暂时把 $n$ 换成 $b$ ，等号右边换位 $m$ ，求解的更一般的形式。 $a x + b y = m$ 根据裴蜀定理：对于任意整数 $a$ , $b$ , $m$ ，求解未知整数 $x$ , $y$ 时，必须满足 $g c d (a, b) ∣ m$ ，即 $m$ 是 $g c d (a, b)$ 的倍数时才有解。
所以我们将计就计，如果 $m$ 是 $g c d (a, b)$ 的一倍，也就是 $m = g c d (a, b)$ ，先解出方程 $a x + b y = g c d (a, b)$ 的解 $x_1$ , $y_1$ ,然后两边乘以 $m / g c d (a, b)$ ，不就能求出来我们想要的了吗？ $a\frac{mx_1}{gcd(a,b)}+b\frac{my_1}{gcd(a,b)}=m$ 所以，我们进一步研究问题：解出方程 $a x + b y = g c d (a, b)$ 的解。
那么我们需要求出三个东西， $x$ ， $y$ ， $g c d (a, b)$ ，这就是扩展欧几里得算法的根本研究问题。（By the way，欧几里得算法就是求解 $g c d (a, b)$ ，方法就是我们熟知的辗转相除法。）
当 $b = 0$ ，有特解 $x = 1, y = 0$ ，这是迭代的初始条件。
当 $b\neq0$ ，假设 $x_1$ ， $y_1$ 是 $ax_1+by_1=gcd(a,b)$ 的解，根据欧几里得算法： $gcd(b,a\ mod\ b)$ ,下一步我们构造 $bx_2+(a\ mod\ b)y_2 = gcd(b, a\ mod\ b)$ ,
那 $a\ mod\ b$ 怎么表示？不就是 $a / b$ 的余数嘛，所以你细品：a%b = a - (a//b)*b，( $\div b = q……r$ ，则 $a = b * q + r$ ,其中q就是a整除b的结果a//b)，带入到上式则有 $bx_2+(a\ mod\ b)y_2 = bx_2+(a - (a//b)b)y_2 = gcd(b,a\ mod\ b)$
好乱，整理一下：
$\left\{ \begin{aligned} ax_1 + by_1 &= gcd(a,b) \\ bx_2+(a - (a//b)b)y_2 &= gcd(b,a\ mod\ b) \\ gcd(a,b) &= gcd(b,a\ mod\ b) \end{aligned} \right.$ 这样我们就能找到 $x_1,y_1)$ 和 $x_2,y_2)$ 的关系了： $ax_1+by_1 = ay_2 + b(x_2 - (a//b)y_2)$ ，所以有 $\left\{ \begin{aligned} x_1 &= y_2\\ y_1 &= x_2 - (a//b)y_2 \end{aligned} \right.$ 这就是递归的关系式。
有了初始值与递归关系，就可以写代码来求解了。

def exgcd(a,b):if b==0:return a,1,0gcd,x2,y2 = exgcd(b,a%b)x1,y1 = y2,x2-(a//b)*y2return gcd,x1,y1

别忘了我们求的是 $a x + b y = g c d (a, b)$ ，而我们要求的是 $a x + b y = m$ ，那么对于函数输出，还要再乘以 $m / g c d$

def Func(a,b,m):gcd,x1,y1 = exgcd(a,b)if m % gcd != 0:return None,None,Nonex0, y0 = x * m // gcd, y * m // gcdreturn gcd, x0, y0

汇总：

def exgcd(a,b):if b==0:return a,1,0gcd,x2,y2 = exgcd(b,a%b)x1,y1 = y2,x2-(a//b)*y2return gcd,x1,y1def Func(a,b,m):gcd,x1,y1 = exgcd(a,b)if m % gcd != 0:return None,None,Nonex0, y0 = x * m // gcd, y * m // gcdreturn gcd, x0, y0MOD = 1e9+7
a = int(input())
_, inv_a, _ = Func(a, MOD, 1)
print(inv_a)

三、费马小定理

费马小定理：
如果 $p$ 是素数，且 $a$ 是一个不能被 $p$ 整除的整数，那么： $a^{p-1}\equiv1({\mathrm{mod}}p)$

这给了我们一个求逆元的好方法： $aa^{p-2}\equiv1(mod\ p)$ 注意前提：模数为素数，且 $a$ 不能被 $p$ 整除。
这时我们只需要算一下 $a^{p-2}$ 就行了，很方便吧。可以用快速幂来求。

def KSM(a, b, mod):if b == 0: return 1if b == 1: return a % modres = KSM(a, b//2, mod)res = res * res % modif b % 2 == 1:res = res * a % modreturn resdef INV(a):return KSM(a, MOD-2, MOD)MOD = 1e9+7
a = int(input())
print(INV(a))

四、总结

介绍了两种方法求解逆元：扩展欧几里得算法和费马小定理算法，前者实用性广，而后者有一个前提，即模数必须为素数，不过一般用费马小定理的情况要多一些。

【蓝桥杯】Python算法——求逆元的两种算法

目录零、前言一、逆元二、扩展欧几里得算法三、费马小定理四、总结零、前言距离25年蓝桥杯还有大概三个月时间，接下来重点应该会放在蓝桥杯备考方向，一起努力，一起加油一、逆元什么是逆元？这是数论中的一个基本概念。如果存…...

编程日记 2025/8/5 5:29:21

音频语言模型与多模态体系结构

音频语言模型与多模态体系结构多模态模型正在创造语言、视觉和语音等以前独立的研究领域的协同效应。这些模型使用通用架构，将每种模式视为不同的“token”，使它们能够以一种与人类认知非常相似的方式联合建模和理解世界。可以将多模态分为两个主要领域：输入空间（…...

编程日记 2025/8/5 5:25:57

Redis的安装和配置、基本命令

一、实验目的本实验旨在帮助学生熟悉Redis的安装、配置和基本使用，包括启动Redis服务、使用命令行客户端进行操作、配置Redis、进行多数据库操作以及掌握键值相关和服务器相关的命令。二、实验环境准备 1. JAVA环境准备：确保Java Development Kit …...

编程日记 2025/7/31 21:51:00

2025.1.17——三、SQLi regexp正则表达式|

题目来源：buuctf [NCTF2019]SQLi1 目录一、打开靶机，整理信息二、解题思路 step 1：正常注入 step 2：弄清关键字黑名单 1.目录扫描 2.bp爆破 step 3：根据过滤名单构造payload step 4：regexp正则注…...

编程日记 2025/8/1 18:11:27

flutter 常用UI组件

文章目录 1. Toast 文本提示框oktoastbot_toast2. loading 加载窗flutter_easyloading3. 对话框gex dialog4.下拉刷新pull_to_refresh5. pop 窗custom_pop_up_menu6. pin code 密码框pinput7. 二维码qr_flutter8. swiper 滚动组件carousel_sliderflutter_swiper_view9. Badge 角…...

编程日记 2025/8/5 5:26:56

基于微信小程序的健身房预约管理系统

作者：计算机学姐开发技术：SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等，“文末源码”。专栏推荐：前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码精品专栏：…...

编程日记 2025/7/31 1:16:42

Windows远程桌面网关出现重大漏洞

微软披露了其Windows远程桌面网关（RD Gateway）中的一个重大漏洞，该漏洞可能允许攻击者利用竞争条件，导致拒绝服务（DoS）攻击。该漏洞被标识为CVE-2025-21225，已在2025年1月的补丁星期二更新中得到…...

编程日记 2025/8/5 5:29:04

如何学习Transformer架构

Transformer架构自提出以来，在自然语言处理领域引发了革命性的变化。作为一种基于注意力机制的模型，Transformer解决了传统序列模型在并行化和长距离依赖方面的局限性。本文将探讨Transformer论文《Attention is All You Need》与Hugging Face Transform…...

编程日记 2025/8/4 16:23:36

RPA赋能内容创作：打造小红书入门词语图片的全自动化流程

🌟 嗨，我是LucianaiB！ 🌍 总有人间一两风，填我十万八千梦。 🚀 路漫漫其修远兮，吾将上下而求索。用RPA全自动化批量生产【入门词语】图片做小红书商单，保姆级工具开发教程最近由…...

编程日记 2025/8/2 22:56:09

Quantum supremacy using a programmable superconducting processor 全文翻译，配公式和图

2019年，谷歌的量子霸权文章， 原文链接： https://www.nature.com/articles/s41586-019-1666-5 第一稿，公式和视图后续再加。。。 Quantum supremacy using a programmable superconducting processor 使用可编程超导处理器的量…...

编程日记 2025/8/5 5:25:59

Jupyter notebook中运行dos指令运行方法

Jupyter notebook中运行dos指令运行方法目录 Jupyter notebook中运行dos指令运行方法一、DOS(磁盘操作系统）指令介绍1.1 DOS介绍1.2 DOS指令1.2.1 DIR - 显示当前目录下的文件和子目录列表。1.2.2 CD 或 CHDIR - 改变当前目录1.2.3 使用 CD .. 可以返回上一级目录1…...

编程日记 2025/8/5 5:29:19

个人vue3-学习笔记

声明：这只是我个人的学习笔记（黑马），供以后复习用。一天学一点，随时学随时更新。明天会更好的！这里只给代码，不给运行结果，看不出来代码的作用我也该进厂了。。。。。 Day1 使用create-vue创建项目。 1.检查版本。 node -v 2.创建项目 npm init vue@latest 可…...

编程日记 2025/8/4 18:00:41

Ubuntu安装搜狗输入法

Ubuntu安装搜狗输入法官网完整安装步骤调整默认输入法官网搜狗输入法 - 官网：https://shurufa.sogou.com/ 搜狗输入法Linux版 - 首页：https://shurufa.sogou.com/linux 搜狗输入法Linux版 - 安装指南：https://shurufa.sogou.com/linux/gu…...

编程日记 2025/8/3 10:10:46

【C】链表算法题2 -- 反转链表

leetcode链接https://leetcode.cn/problems/reverse-linked-list/description/https://leetcode.cn/problems/reverse-linked-list/description/https://leetcode.cn/problems/reverse-linked-list/description/https://leetcode.cn/problems/reverse-linked-list/description/…...

编程日记 2025/8/1 9:49:25

1.7 ChatGPT：引领AI对话革命的致胜之道

ChatGPT：引领AI对话革命的致胜之道随着人工智能（AI）技术的迅猛发展，特别是在自然语言处理（NLP）领域，OpenAI 的 ChatGPT 已经成为了举世瞩目的技术突破。从普通的自动化客服到深入的创作与协作，ChatGPT 通过其卓越的语言理解和生成能力，改变了人们与计算机交互的方式…...

编程日记 2025/8/4 21:38:11

当设置dialog中有el-table时，并设置el-table区域的滚动，看到el-table中多了一条横线

问题：当设置dialog中有el-table时，并设置el-table区域的滚动，看到el-table中多了一条横线； 原因：el-table有一个before的伪元素作为表格的下边框下，初始的时候已设置，在滚动的时候并没有重新设置…...

编程日记 2025/8/2 19:17:42

如何使用 useMemo 和 memo 优化 React 应用性能？

使用 useMemo 和 memo 优化 React 应用性能在构建复杂的 React 应用时，性能优化是确保应用流畅运行的关键。React 提供了多种工具来帮助开发者优化组件的渲染和计算逻辑，其中 useMemo 和 memo 是两个非常有用的 Hook。本文将详细介绍这两个工具的使用方…...

编程日记 2025/8/2 13:48:09

turtle教学课程课堂学习考试在线网站

完整源码项目包获取→点击文章末尾名片！...

编程日记 2025/7/18 17:53:54

spark任务优化参数整理

以下参数中有sql字眼的一般只有spark-sql模块生效，如果你看过spark的源码，你会发现sql模块是在core模块上硬生生干了一层，所以反过来spark-sql可以复用core模块的配置，例外的时候会另行说明，此外由于总结这些参数是在不…...

编程日记 2025/8/4 22:37:35

TCP TIME-WAIT 状态为什么要坚持 2MSL

经常有人问这个问题，这种问题问我就对了。我准备了下面的一幅时序图来解释这个问题： 简单点说就是两个目的： 正常处理被动关闭方的重传 FIN；确保当前连接的所有报文全部消失。也就是说，无论任何情况下，…...

编程日记 2025/8/5 5:27:38

如何在Ubuntu上安装Cmake

前言本文主要阐述如何在Ubuntu22.04上面安装cmake，具体可看下面的操作。正文一、环境 Ubuntu22.04 cmake-3.31.4.tar.gz 二、步骤参考这个方案： 【运维】Ubuntu如何安装最新版本的Cmake，编译安装Cmake，直接命令安装…...

编程日记 2025/8/5 5:27:40

1.17学习

crypto nssctf-[SWPUCTF 2021 新生赛]crypto8 不太认识这是什么编码，搜索一下发现是一个UUENCODE编码，用在线工具UUENCODE解码计算器—LZL在线工具解码就好 misc buuctf-文件中的秘密下载附件打开后发现是一个图片，应该是一个图片隐写&…...

编程日记 2025/8/5 5:29:06

力扣搜索二维矩阵

二分查找，闭区间与开区间的不同解法。题目乍一看，不是遍历一下找到元素就可以了。 class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] ints : matrix) {for (int ans : ints) {if (ans target) return true;}}…...

编程日记 2025/7/30 18:37:20

RabbitMQ基础篇

文章目录 1 RabbitMQ概述1.1 消息队列1.2 RabbitMQ体系结构 2 RabbitMQ工作模式2.1 简单模式（Simple Queue）2.2 工作队列模式（Work Queues）2.3 发布/订阅模式（Publish/Subscribe）2.4 路由模式（R…...

编程日记 2025/7/30 19:49:10

【springboot】Spring 官方抛弃了 Java 8！新idea如何创建java8项目

解决idea至少创建jdk17项目问题 idea现在只能创建最少jdk17，不能创建java8了吗?解决问题 idea现在只能创建最少jdk17，不能创建java8了吗我本来以为是 IDEA 版本更新导致的 Bug，开始还没在意。直到我今天自己初始化项目时才发现&am…...

编程日记 2025/7/31 16:49:19

[BrainShadow-V1] VR头戴设备统计报告

Brain-Shadow-V1 EventVR headsetsReported byXiao enDate2025/01/15Version1.0 HTC Vive Pro 2 Pro HTC Vive Pro 2 是一款高端虚拟现实头显，配备双 2.5K 显示屏，组合分辨率达到 48962448，提供 120 的视场角和 120Hz 的刷新率。该设备支持…...

编程日记 2025/8/5 1:21:30

RK3568 Android11 锁屏界面屏蔽下拉状态栏

参考文章： Android R锁屏界面屏蔽下拉状态栏_pulseexpansionhandler-CSDN博客前提增加状态栏控制显隐属性，以下面文章为前提补充功能 RK3568 Android11 状态栏和导航栏增加显示控制功能-CSDN博客修改文件位置： frameworks/base/package…...

编程日记 2025/8/5 5:26:58

53，【3】BUUCTF WEB october 2019 Twice SQLinjection

题目得到信息，2次注入，进入靶场登录页面，很自然想到SQL 第一次注入应该是这个可以登录，注册，提交简介的页面第二次注入应该是在info处注入，信息显示在简介处我真的纯脑子有病，人家二次注入不…...

编程日记 2025/8/5 1:33:12

利用硬盘虚拟内存解决华为手机模拟器运行内存不足问题

在进行鸿蒙开发时，华为手机模拟器是必不可少的工具。然而，对于只有 8GB 物理内存的电脑来说，运行模拟器可能会遇到 "系统内存不足" 的提示，导致模拟器无法正常启动。这时，我们可以通过硬盘虚拟出额外的内存来…...

编程日记 2025/8/3 23:43:35

探秘Shortest与Stagehand：开启高效测试与自动化新篇

探秘Shortest与Stagehand：开启高效测试与自动化新篇在数字化浪潮的推动下，网页自动化工具如同繁星般涌现，为众多行业带来了效率的变革。在这些工具中，Shortest和Stagehand凭借其出色的表现，成为了众多开发者、测试人…...

编程日记 2025/8/5 5:25:59

网络安全构成要素

一、防火墙组织机构内部的网络与互联网相连时，为了避免域内受到非法访问的威胁，往往会设置防火墙。使用NAT（NAPT）的情况下，由于限定了可以从外部访问的地址，因此也能起到防火墙的作用。二、IDS入侵检…...

编程日记 2025/8/4 5:35:57

家政服务小程序，打造智慧家政新体验

春节即将来临，家政市场呈现出了火热的场景，大众对家政服务的需求持续增加。近年来，家政市场开始倾向数字化、智能化，借助科学技术打造家政数字化平台，让大众在手机上就可以预约家政服务，减少传统家政市场…...

编程日记 2025/8/5 5:26:57

2.使用Spring BootSpring AI快速构建AI应用程序

Spring AI 是基于 Spring Boot3.x 框架构建，Spring Boot官方提供了非常便捷的工具Spring Initializr帮助开发者快速的搭建Spring Boot应用程序,IDEA也集成了此工具。本文使用的开发工具IDEASpring Boot 3.4Spring AI 1.0.0-SNAPSHOTMaven。 1.创建Spring Boot项目 …...

编程日记 2025/8/5 5:23:05

OpenCV实战-全景图像拼接

代码地址见文末实现效果 1. 项目背景随着计算机视觉技术的不断发展，图像拼接技术已被广泛应用于虚拟现实、地图生成、全景摄影等领域。图像拼接（Image Stitching）旨在将多张部分重叠的图像无缝拼接成一幅完整的全景图像。此任务要求图像处…...

编程日记 2025/8/5 5:29:04

h5使用video播放时关掉vant弹窗视频声音还在后台播放

现象： 1、点击遮罩弹窗关闭，弹窗的视频已经用v-if销毁，但是后台会自己从头开始播放视频声音。但是此时已经没有视频dom 2、定时器在打开弹窗后3秒自动关闭弹窗，则正常没有问题。原来的代码： //页面 <a click&quo…...

编程日记 2025/8/5 5:26:00

解决leetcode第3418题机器人可以获得的最大金币数

3418.机器人可以获得的最大金币数难度：中等问题描述： 给你一个mxn的网格。一个机器人从网格的左上角(0,0)出发，目标是到达网格的右下角(m-1,n-1)。在任意时刻，机器人只能向右或向下移动。网格中的每个单元格包含一个值coin…...

编程日记 2025/8/4 5:28:42

anaconda安装和环境配置

文章目录一、Anaconda下载1.从官网直接下载：2.从镜像站中下载： 二、Anaconda安装三、检测是否有Anaconda配置anaconda环境四、 Anaconda创建多个python环境（方便管理项目环境）1.查看conda有哪些环境2.创建python3.6的环境3.激活…...

编程日记 2025/7/31 20:35:12

Lora理解QLoRA

Parameter-Efficient Fine-Tuning (PEFT) ：节约开销的做法，fine-tune少量参数，而不是整个模型； Low-Rank Adaptation (LoRA) ：是PEFT的一种；冻结原参数矩阵，只更新2个小参数矩阵。原文经过对比…...

编程日记 2025/8/4 14:17:11

嵌入式杂谈——什么是DMA？有什么用？

什么是DMA？——直接内存访问技术详解在嵌入式系统和计算机体系结构中，DMA（Direct Memory Access，直接内存访问） 是一种重要的数据传输技术。它允许外设（如UART、SPI、ADC等）直接与内存进行数据…...

编程日记 2025/8/3 7:18:15

超标量处理器设计2-cache

1. cache 介绍影响Cache缺失的情况有3种： Compulsory: 第一次被访问的指令或者数据肯定不会在cache中，需要通过预取来减少这种缺失Capcity: Cache容量越大，缺失就可以更少, 程序频繁使用的三个数据来源于3个set， 但是&#xff…...

编程日记 2025/8/4 7:26:23

使用Nginx正向代理让内网主机通过外网主机访问互联网

目录环境概述流程说明在外网服务器上安装部署nginx? 安装前准备下载nginx ?编译安装nginx 开始配置正向代理创建systemd服务单元文件，用于管理Nginx服务的启动、停止和重新加载启动nginx ?代理服务器本地验证 ?内网服务器验证 ?将代理地址添…...

编程日记 2025/8/4 19:13:07

蓝桥杯刷题第二天——背包问题

题目描述有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是Vi价值是Wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V&am…...

编程日记 2025/8/1 21:41:35

DM达梦启用及收集AWR报告

1.创建DBMS_WORKLOAD_REPOSITORY系统包查看DBMS_WORKLOAD_REPOSITORY系统包启用状态 SQL> SELECT SF_CHECK_AWR_SYS;LINEID SF_CHECK_AWR_SYS ---------- ---------------- 1 0SF_CHECK_AWR_SYS 返回值 0：未启用；1：已启…...

编程日记 2025/8/3 8:20:37

【git】如何删除本地分支和远程分支？

1.如何在 Git 中删除本地分支本地分支是您本地机器上的分支，不会影响任何远程分支。 （1）在 Git 中删除本地分支 git branch -d local_branch_name git branch 是在本地删除分支的命令。-d是一个标志，是命令的一个选项&#x…...

编程日记 2025/8/1 17:33:10

pix2pix mmgeneration通用场景黑白图片上色模型训练，Docker

https://www.dong-blog.fun/post/1924 对于机器学习和深度学习感兴趣的读者来说，OpenMMLab 提供的 MMGeneration 库是一个绝佳的选择。最近我在阅读一篇关于 MMGeneration 的博客文章，尤其是在使用 Docker 环境进行模型和算法测试方面，受益匪浅。以下是我对目标博客内容的概…...

编程日记 2025/7/31 7:41:39

【Redis入门到精通六】在Spring Boot中集成Redis（含配置和操作演示）

目录 Spring Boot中集成Redis 1.项目创建和环境配置 2.基本操作演示 Spring Boot中集成Redis Spring社区也自定义了一套Redis的客户端，与jedis的操作方式有所差异，Spring中把每个类型的操作都单独封装了起来。下面就让我来带大家了解如何在Spring Bo…...

编程日记 2025/8/1 11:17:27

js使用qrcode与canvas生成带logo的二维码

qrcode库文档 https://www.npmjs.com/package/qrcode 安装 npm i qrcode 使用 errorCorrectionLevel: H // 容错率（H是最高，其它看文档） width: 200 // 大小 margin: 2 // 边距 import QRCode from qrcodeconst testFn async () > {c…...

编程日记 2025/8/2 21:06:24

【STM32】LED状态翻转函数

1.利用状态标志位控制LED状态翻转在平常编写LED状态翻转函数时，通常利用状态标志位实现LED状态的翻转。如下所示： unsigned char led_turn_flag; //LED状态标志位，1-点亮，0-熄灭/***************************************函…...

编程日记 2025/8/2 22:49:25