【算法基础 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理)

本文主要是介绍【算法基础 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 为什么需要逆元
  • 逆元的概念
    • 1.单位元
    • 2.逆元
    • 3.模乘的单位元
    • 4.模乘的逆元
  • 开始求逆元
    • 1.扩展欧几里得定理
    • 2.费马小定理


原文链接

为什么需要逆元

首先,在算法竞赛中,很多情况下会遇到数值很大的数据,这个时候,题目往往会让我们对某个数去摸,来控制数据范围。

在±*运算中,我们可以对每个数单独取模,然后再对运算之后的数取模。

但是除法比较特殊,例如: ( 40 ÷ 5 ) m o d 10 ≠ ( ( 40 m o d 10 ) ÷ ( 5 m o d 10 ) ) ) m o d 10 (40\div5)mod 10\neq((40mod 10)\div(5mod 10)))mod10 (40÷5)mod10=((40mod10)÷(5mod10)))mod10

那我们可以将其转化为乘法,就相当于:除以一个数,就是乘以一个数的倒数

这个时候就要用到逆元

逆元的概念

1.单位元

在一个集合中,对于某种运算,如果对于任何的集合元素a和元素e运算,得到还是集合元素a本身,就称e为这个运算下的单位元

  • 例如

在加法中:对任意实数a: a + e = e + a = a a + e = e + a = a a+e=e+a=a, 则e为单位元, e = 0 e = 0 e=0
在乘法中:对任意实数a: a × e = e × a = a a \times e = e \times a = a a×e=e×a=a, 则e为单位元, e = 1 e = 1 e=1
(每种运算都有自己的单位元)

2.逆元

在一个集合中,对于某种运算,如果任意两个元素的运算结果等于单位元,则称这两个元素互为逆元

  • 例如

在加法中:对任意实数a: a + − a = 0 a + -a = 0 a+a=0, 而0是加法的单位元,则-a为加法的逆元
在乘法中:对任意实数a: a × a − 1 = 1 a \times a^{-1} = 1 a×a1=1,则 a − 1 a^{-1} a1为乘法的逆元

3.模乘的单位元

对于模 n n n乘法,所有模 n n n a a a同余的数都可以表示成:
a ( m o d n ) = k n + a ( k ∈ Z ) a(mod~n)=kn+a~~(k\in Z) a(mod n)=kn+a  (kZ)
令单位元为 e ( m o d n ) e(mod~n) e(mod n),将 a ( m o d n ) a(mod~n) a(mod n) e ( m o d n ) e(mod~n) e(mod n)进行模乘运算,得到:
a ( m o d n ) × e ( m o d n ) = ( k 1 n + a ) ( k 2 n + e ) = ( k 1 k 2 n 2 + k 1 e n + k 2 a n + a e ) = ( k 1 k 2 n + k 1 e + k 2 a ) n + a e \begin{equation*} %加*表示不对公式编号 \begin{split} & a(mod~n)\times e(mod~n)\\ & = (k_1n+a)(k_2n+e)\\ & =(k_1k_2n^2+k_1en+k_2an+ae)\\ & =(k_1k_2n+k_1e+k_2a)n+ae\\ \end{split} \end{equation*} a(mod n)×e(mod n)=(k1n+a)(k2n+e)=(k1k2n2+k1en+k2an+ae)=(k1k2n+k1e+k2a)n+ae

根据单位元定义,
a ( m o d n ) × e ( m o d n ) = a ( m o d n ) a(mod~n)\times e(mod~n) = a(mod~n) a(mod n)×e(mod n)=a(mod n)

带入定义式:
( k 1 k 2 n + k 1 e + k 2 a ) n + a e = k n + a (k_1k_2n+k_1e+k_2a)n+ae = kn+a (k1k2n+k1e+k2a)n+ae=kn+a


{ k = k 1 k 2 n + k 1 e + k 2 a e = 1 \begin{cases} k = k_1k_2n+k_1e+k_2a\\ e = 1\\ \end{cases} {k=k1k2n+k1e+k2ae=1

也就是说,模乘的单位元是1

4.模乘的逆元

模乘运算中,任意整数 a ( m o d n ) a(mod~n) a(mod n)的逆元表示为:
a − 1 ( m o d n ) a^{-1}(mod~n) a1(mod n)
根据定义,满足:
a a − 1 ≡ 1 ( m o d n ) aa^{-1}\equiv 1(mod~n) aa11(mod n)

可以理解为 a a a a − 1 a^{-1} a1 n n n的作用下发生了反应,变成了1

但是,不像加减法和乘除法每个数(乘除法除0以外)都有逆元

对于每个数 a a a均有唯一的与之对应的乘法逆元 x x x,使得 a x ≡ 1 ( m o d n ) ax\equiv 1(mod~n) ax1(mod n)
逆元存在的充要条件: g c d ( a , n ) = 1 gcd(a,n)=1 gcd(a,n)=1(这个数和模数互质)

此时,在模 n n n的意义下,一个数 a a a如果有逆元 x x x,那么除以 a a a就相当于乘以 x x x

开始求逆元

如何在给定 a a a n n n的前提下给出逆元?

先在这里附上欧几里得定理

1.扩展欧几里得定理

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式 a x + b y = g c d ( a , b ) ax + by = gcd(a,b) ax+by=gcd(a,b)

扩展欧几里得常用来求形如方程:ax + by = c 的整数通解或者特解。

等式方程 ax+by = c 是不一定有整数解x、y的
但是已知:若 c c%gcd(a,b)=0 c,则方程 a x + b y = c ax + by = c ax+by=c必定存在整数解,否则必定无解(其推导如下)。
对于最简单的情况: 对于不完全为0的非负整数 a , b , g c d ( a , b ) a,b,gcd(a, b) a,b,gcd(a,b) 表示 a , b a,b a,b的最大公约数,必定存在整数对 x , y x, y x,y满足 a × x + b × y = = g c d ( a , b ) a\times x+b\times y==gcd(a, b) a×x+b×y==gcd(a,b)。 我们一般根据欧几里算法与最大公约数的关系由最简单的情况来拓展推导方程的通解。

已知:a % gcd(a,b) == 0,b % gcd(a,b) == 0;若整数x、y为方程 ax + by = c 的一组解
则 ax % gcd(a,b) == 0,by % gcd(a,b) == 0
则 ax + by % gcd(a,b) == 0
即 c % gcd(a,b) == 0
因此 方程 ax + by = c 有解的充要条件是 c % gcd(a,b) == 0
————————————————
版权声明:本文为CSDN博主「阿阿阿安」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_40772692/article/details/81183174

  • 下面举一个例子

【例题】给定正整数 a , b a,b a,b,求满足等式 a x + b y = 1 ax+by=1 ax+by=1 x x x的最小正整数解。如果不存在,返回-1。

首先找出 a , b a,b a,b的最大公约数,令 g = g c d ( a , b ) g = gcd(a,b) g=gcd(a,b)
则,原式可以转化为:
g ( a g x + b g y ) = 1 g(\frac{a}{g}x+\frac{b}{g}y) = 1 g(gax+gby)=1
如果 a b = 1 ( a , b ∈ Z + ) ab = 1~~(a,b\in Z^+) ab=1  (a,bZ+),则 a = 1 , b = 1 a=1, b=1 a=1,b=1

所以 g = 1 g = 1 g=1

所以,只需要考虑 a , b a,b a,b互素的情况

下面给出扩展欧几里得定理的代码:

int extend_gcd(int a,int b,int &x,int & y)
{if(b == 0){x = 1;y = 0;return a;}// x,y调换传给下一次递归等价于x1 = y2int t = extend_gcd(b,a%b,y,x);//等价y1 = x2 -(a/b) * y2y -= a / b * x;return t;
}

那上面这个跟逆元有什么联系呢?
来看这道题

【例题】给定正整数 p p p a a a,求满足 a x ≡ 1 ( m o d p ) ax\equiv 1(mod~p) ax1(mod p)的最小正整数 x x x,如果不存在,返回-1

乍看上去跟上面一点关系都没有
将原式换成:
a x = k n + 1 ( k ∈ Z ) ax = kn+1~~(k\in Z) ax=kn+1  (kZ)
移项后得到
a x − k n = 1 ax-kn = 1 axkn=1
由于k是个整数,不分正负,所以可以表示为
a x + k n = 1 ax+kn = 1 ax+kn=1
于是,可表示为
a x + b y = 1 ax+by = 1 ax+by=1

ll inv(ll a, ll n){ll x, y;ExpGcd(a, n, x, y);x = (x % n + n) % n;return x;
}

2.费马小定理

b b b存在乘法逆元的充要条件是 b b b与模数 m m m互质。当模数 m m m为质数时, b m − 1 ≡ 1 ( m o d m ) b^{m-1}\equiv 1(mod~m) bm11(mod m), b m − 2 b^{m-2} bm2为b的逆元

【例题】给定素数 p p p和正整数 a a a,求满足 a x ≡ 1 ( m o d p ) ax\equiv 1(mod~p) ax1(mod p)的最小正整数 x x x,如果不存在,返回-1

a a a p p p的倍数时, a x ≡ 0 ( m o d p ) ax\equiv 0(mod~p) ax0(mod p),所以一定不存在
当不是倍数(a和p互质), a p − 1 ≡ 1 ( m o d p ) ⇒ a × a p − 2 ≡ 1 ( m o d p ) a^{p-1}\equiv 1(mod~p) \Rightarrow a\times a^{p-2}\equiv 1(mod~p) ap11(mod p)a×ap21(mod p)

此时 a p − 2 a^{p-2} ap2就是a的逆元

  • 这道题就是求的 a p − 2 a^{p-2} ap2,考的费马定理和快速幂

题目描述:给定 n n n a i , p i a_i,p_i ai,pi,其中 p i p_i pi 是质数,求 a i a_i ai p i p_i pi的乘法逆元,若逆元不存在则输出 impossible

注意:请返回在 0 ∼ p − 1 0∼p−1 0p1 之间的逆元。

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;LL qmi(int a, int b, int p){LL res = 1 % p;while(b){if(b & 1) res = res * a % p;a = a * (LL)a % p;b >>= 1;}return res;
}int main(){int n, a, p;cin >> n;while(n--){cin >> a >> p;int res = qmi(a, p - 2, p);if(a % p) cout << res << endl;      //保证a不是p的倍数else cout << "impossible" << endl;}return 0;
}

这篇关于【算法基础 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s