[人工智能]酸菜鱼的我今天在学习逆元

逆元是什么

当（a * c）% p = 1时 ，称c为a的逆元。

逆元的用法

性质大家都知道，取余的时候有如下（同余拆分定理），但是当（a / b）% p 的时候该怎么办呢？这个时候我们就需要用上逆元了。

(a + b) % p = a % p + b % p(a - b) % p = a % p - b % p(a * b) % p = a % p * b % p(a / b) % p = ?

让除数乘它的逆元，将除法转化为乘法进行计算。 （逆元的符号为inv() ）。

(a / b) % p = (a * inv(b) ) % p

逆元的证明

原式：

(a / b) % p

证明：

a / b = a 乘 b 的-1次方（打不出来-1次方就这么写了。）

(b * c) % p = 1 -> 1/ b = c % p

a * （b的-1次方）= a * (c % p)

原式可化为：(a * (c % p)) % p = a % p * (c % p) % p = a % p * c % p = (a * c) % p

又因为：c是b的逆元 ，原式最终可化为：(a * inv(b) ) % p

逆元的求法

1、费马小定理

费马小定理(Fermat's little theorem)是中的数论一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

a ^ (p - 1) = 1 (mod p)    左右同时再除以aa ^ (p - 2) = 1 / a (mod p)a ^ (p - 2) = inv(a) (mod p)inv(a) = a ^ (p - 2) (mod p)

(特意说明一下，mod p 就是 % p)

代码如下（用到快速幂）：

int num (a , p) {//求a的p-2次方对p取余    int b = p - 2;    int res = 1;    while (b) {        if (b & 1) res *= (res * a) % p;        a = (a * a) % p;        b >>= 1;    }    return res;}

2、扩展欧几里得算法

扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数,此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

gcd (a , p) = 1a * x + p * y = 1    左右同时对p取模a * x (mod p) = 1 (mod p)    左右同时除以ax (mod p) = 1 / a (mod p)x (mod p) = inv(a) (mod p)

代码不知道怎么写，先欠着，hh。

（如有错误，欢迎指正）

?