逆元相关知识点、求法(快速幂,拓展欧几里得,线性算法,阶乘的逆元)及拓展欧几里得算法的应用

本文主要是介绍逆元相关知识点、求法(快速幂,拓展欧几里得,线性算法,阶乘的逆元)及拓展欧几里得算法的应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

概念:

若xy≡1 (mod p),且gcd(x,p)=1(gcd函数是求x,y的最大公约数),则称x关于模p的乘法逆元为y。
那么除以y相当于乘以x(模p情况下)。值得注意的是x
(y+k*p)≡1(mod p),逆元不止一个,求最小的就可以;

几个定理or算法:

1.费马小定理:x^(p-1) ≡1 (mod p),p为素数,x不为p的倍数,若x为p的倍数则x^p ≡p (mod p)。那么当gcd(x,p)=1时,x * x^(p-2) ≡ 1(mod p),即x关于模p的逆元为x^(p-2)。则快速幂可求得逆元。

2.欧拉定理:a^φ(n)≡1(mod n) ,gcd(a,n)=1,函数φ(n)求数1到n与n互质的数的个数,当n为素数p的时候则为费马小定理。

3.欧几里得算法:即辗转相除法。

4.扩展欧几里得算法:已知整数a, b一定可以求解一组x,y(整数),使它们满足贝祖等式: ax+by = gcd(a, b) =d。

5 贝祖定理,方程ax+by=c有整数解的条件是gcd(a,b) | c。

用法:
1)这个算法可以用来求已知a,b的二元一次方程ax+by =z的整数解。但是前提是gcd(a,b) | z,否则没有整数解。(增加一个判断,例题POJ1061青蛙的约会)

2) 还可以用来求乘法的逆元a∗x≡1(mod p)—>a∗x+y∗p=1—>a∗x+b∗y=1(把p换成b),那么x是a关于b( p )的乘法逆元,y是b( p )的关于a的乘法逆元。(gcd(a*x,b)=1,b=p)

然而无论是用来求整数解还是求逆元都要对贝祖方程求解。

具体求法,代码及例题

拓展欧几里得算法:

1 求法

首先要对贝祖方程进行求解:
1)当b=0时,gcd(a,b)=a , ax+by=a–>x=1,y=0
2) 当b!=0时,
设方程1:ax+by=gcd(a,b),
方程2:bx1+(a%b)x1=gcd(b,a%b)
由欧几里得算法可得gcd(a,b)=gcd(b,a%b)=…=gcd(c,0) (///欧几里得算法的递推过程,c为a,b的最大公约数)
那么ax+by=bx1+(a-a/b*b)y1—>ax+by=ay1+b(x1-a/by1)—>x=y1 , y=x1-a/by1,由此我们可以知道x,y的解可由下一个x1,y1的解的得到,而递归到最后时,b=0,gcd(a,b)=a , ax+by=a–>x=1,y=0,这个时候x,y的值根据x=y1 , y=x1-a/by1一层一层的往回带,最后可以得到初始的x,y值。

2 代码:

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(a==0&&b==0) return -1;///注意这种极端情况if(b==0){x=1,y=0;return a;}int r=exgcd(b

这篇关于逆元相关知识点、求法(快速幂,拓展欧几里得,线性算法,阶乘的逆元)及拓展欧几里得算法的应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/646128

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级(QoS0/1/2),以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端(Clien

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布局和层叠关

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

CSS3中的字体及相关属性详解

《CSS3中的字体及相关属性详解》:本文主要介绍了CSS3中的字体及相关属性,详细内容请阅读本文,希望能对你有所帮助... 字体网页字体的三个来源:用户机器上安装的字体,放心使用。保存在第三方网站上的字体,例如Typekit和Google,可以link标签链接到你的页面上。保存在你自己Web服务器上的字

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”