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

这篇具有很好参考价值的文章主要介绍了【算法基础 & 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


原文链接

为什么需要逆元

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

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

但是除法比较特殊,例如: ( 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 = y2
	int t = extend_gcd(b,a%b,y,x);
	//等价y1 = x2 -(a/b) * y2
	y -= 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 之间的逆元。文章来源地址https://www.toymoban.com/news/detail-819017.html

#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;
}

到了这里,关于【算法基础 & 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习中的数学——距离定义(一):欧几里得距离(Euclidean Distance)

    分类目录:《机器学习中的数学》总目录 相关文章: · 距离定义:基础知识 · 距离定义(一):欧几里得距离(Euclidean Distance) · 距离定义(二):曼哈顿距离(Manhattan Distance) · 距离定义(三):闵可夫斯基距离(Minkowski Distance) · 距离定义(四):切比雪夫距离(

    2023年04月11日
    浏览(35)
  • Exgcd(拓展欧几里得算法)的初步理解

    若a,b是整数,且 gcd(a,b)=d ,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。它的一个重要推论是:a,b互质的充分必要条件是存在整数x,y使ax+by=1. 针对于一次不定方程 ax+by=c 进行求解,利用以上的裴蜀定理可以进行求解,当然要满足 gcd(a,b)|

    2024年02月16日
    浏览(32)
  • 数论 --- 约数和定理公式推导、最大公约数、欧几里得算法

    和试除法判断一个数是不是质数是一个道理 从小到大枚举所有的约数,如果当前数能整除这个数的话,说明这个数就是当前数的约数 优化,与试除法判断质数是一样的 如果 d 是 n 的约数,n / d 也一定能整除 n,一个数的约数也一定是成对出现的,在枚举的时候也可以只枚举

    2023年04月08日
    浏览(83)
  • 数学_使用舒尔补简化矩阵求逆

    将矩阵化成上三角矩阵,左乘 ,示例解方程如下:   将矩阵化成上三角矩阵,左乘 ,示例解方程如下:  

    2024年02月07日
    浏览(46)
  • 一文看懂什么是欧几里得算法!多图演示辗转相除算法究竟是什么!为什么要这样开展!多图预警!

    ps:全文图片均为手绘,如果有不标准的地方还望谅解,之后会慢慢熟悉画图工具的,感谢感谢!!! 欧几里得算法 又称为 辗转相除法 ,是指用于计算两个非负整数a,b的最大 公约数 。 两个整数的最大公约数是指能够同时整除它们的最大的正整数。 辗转相除法能够实现效

    2024年02月02日
    浏览(47)
  • 快乐地谈谈:关于RSA算法中求私钥d的欧几里得方法(辗转相除法)考试向的欸

    关于RSA算法本身,就提及一下,它是属于非对称密码体制. 基本的加密方式就如下图所示: c为加密后的密文,m为加密前的明文 其中一般会给出公开密钥n、e的值,这样根据规则,便可以实现加密过程。而题目往往需要进行解密,那么就需要 先求解出p、q,随后再求解出私钥

    2024年02月04日
    浏览(37)
  • Shell 编程快速入门 之 数学计算和函数基础

    整数之和 shell程序的数字类型只有整数类型一种,并不支持浮点数。如: 浮点数之和  在shell编程中,浮点数只能被用作字符串来操作,脚本语法本身不提供浮点数的操作方法,但可以调用bc, awk等外部命令来计算并返回结果。如: 两个或多个数的运算只有列出算式计算就行

    2024年02月11日
    浏览(41)
  • 路径规划 | 图解快速随机扩展树RRT算法(附ROS C++/Python/Matlab仿真)

    🔥附C++/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备!详细介绍全局规划(图搜索、采样法、智能算法等);局部规划(DWA、APF等);曲线优化(贝塞尔曲线、B样条曲线等)。 🚀详情:图解自动驾驶中的运动规划(Motion Planning),附几十种规划算法 快速扩展随机扩展树

    2024年02月05日
    浏览(56)
  • 【算法基础】数学知识

    866. 试除法判定质数 - AcWing题库 时间复杂度是logN 867. 分解质因数 - AcWing题库  868. 筛质数 - AcWing题库 朴素版,埃氏筛法  线性筛 868. 筛质数 - AcWing题库 线性筛把时间复杂度优化到O(n),就需要保证筛去一个数只用一次,保证最小质因数就可以确保这一点。 如。筛去24,24=2*1

    2024年02月08日
    浏览(48)
  • 算法通关村-----数字与数学基础问题

    问题描述 已知函数 signFunc(x) 将会根据 x 的正负返回特定值: 如果 x 是正数,返回 1 。 如果 x 是负数,返回 -1 。 如果 x 是等于 0 ,返回 0 。 给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。 返回 signFunc(product) 。 详见leetcode1822 问题分析 最直接的方式是遍

    2024年02月09日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包