【模板】乘法逆元

题目

洛谷P3811乘法逆元

题解

定义:乘法逆元又称数论倒数。若 且a,m互质,则x为a的逆元,记为,若a,m不互质,则不存在逆元。当且仅当m为素数时,a有唯一的乘法逆元。

用途:在模算术中,有以下几个公式:

(a+b) mod p =((a mod p)+(b mod p)) mod p

(a-b) mod p=((a mod p) – (b mod p) + p) mod p

ab mod p=(a mod p)(b mod p)mod p

在模意义下的运算中,这几个公式可以降低运算过程中数据的规模,然而,遇到除法运算时,便会出现问题。下面是个错误的式子:a/b mod p=(a mod p)/(b mod p) mod p 可以举例证伪。在一系列模运算中,被除数和除数可能进行过取模操作,因此无法直接得到正确结果。因此,模意义下的除法要转化成乘法。

一个例子:6/2=3(mod 5) 6*3=3(mod 5)

求逆元方法一(费马小定理):

费马小定理:若p是质数,则对于任意整数a,有

结合快速幂就可以求逆元。缺陷:这种算法必须保证p是质数,而且复杂度较高,不适合批量操作。

求逆元方法二(扩展欧几里得算法):即求同余方程 的解(通常求最小正整数解)。这个算法只要求a,p互质,速度也更快,但也不适合批量操作。

求逆元方法三(线性递推):推导过程如下(第2行到第3行,两边同时乘i和p mod i的逆元)

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月23日 上午9:20

“[计算机]是数学的主人。”