求解逆元 以及求解中的拓展
乘法逆元
作用 | 背景
对于求模运算，有这么几种性质：
我们还可以扩展到交换律和结合律，但是看来看去，却没有除法的身影…
为了除法能够使用这种性质，我们可以把模P意义下的除法转换从模P意义下的乘法，也就是乘法逆元。
逆元定义
若存在这么一种关系，且 a 与 p 互质，那么我们就称 x 为 a 的逆元，记为 a^-1，所以我们也可以称 x 为 a 在 mod b 意义下的倒数，
有了乘法逆元，我们就可以这么做,这样就能使用开头提到的性质啦
接下来要做的就是各种求法求逆元了
利用费马小定理快速幂
费马小定理有几个限制
如果呢，a 为正整数，p 为质数， 且a、p 互质
那么就可以得到这么一条式子
我们可以把式子带入到定义，则有
这样我们只需要求得a^(p - 2)就能得到逆元了，当 p 过大时，我们可以利用快速幂求解
利用扩展欧几里得
扩展欧几里得的作用是求解一个方程的解，好处是，只要求 a, p 互质
而且用于查询单个数的逆元，效率很高
结合以下两条式子，就能求出逆元
逆元定义转换成方程
扩展欧几里得的性质
代码实现
void Exgcd(ll a, ll b, ll &x, ll &y) {if (!b) x = 1, y = 0;else Exgcd(b, a % b, y, x), y -= a / b * x;}int main() {ll x, y; Exgcd (a, p, x, y);x = (x % p + p) % p;printf ("%d\n", x); //x是a在mod p下的逆元return 0;}
线性求一组逆元
当要求1 ~ n 的逆元时，采用扩展欧几里得就慢了，
可以直接使用递推式子求出逆元
我们来证明一下:
令 p = k a + r
写成 k a + r ≡ 0 (mod p)
两边同乘 a^-1 r^-1，得
k r^-1 + a ^ -1 ≡ 0 (mod p)
a ^ -1 ≡ - k r^-1 (mod p)
把 k 和 r 换掉
a ^ -1 ≡ - (p / a) (p % a)^-1 (mod p)
又因为负数取模可以等价于变换的正数 (-x) % p = (-x + p ) % p
所以最终递推公式为
a ^ -1 ≡ (p - p / a) * (p % a)^-1 (mod p)
容易看出，使用线性求逆元，需要 p > n，否则 p / a就等于0了
若有收获，就点个赞吧
0 人点赞
