浅谈乘法逆元

· · 个人记录

一.啥是逆元

若整数b,p互质，且b\mid a，则存在一个整数x,使得\dfrac{a}{b}\equiv a\times x\pmod{p}。称x为b的模p乘法逆元，记为b^{-1}\pmod{p}

能不能整点人能看懂的

人能看懂的来了

若bx\equiv1\pmod{p}，称x为b模p的乘法逆元。前提是x,p互质，否则无解。

 

二.逆元砸球

1.费马小定理

若p为质数，且\gcd(a,p)=1，那么

a^{-1}\equiv1\pmod{p}

读者自证不难

\because a^{-1}\equiv1\pmod{p} \therefore a\times a^{-2}\equiv1\pmod{p}

故a^{-2}是a在模p意义下的乘法逆元，所以就可以用快速幂求解

2.扩欧（不知道啥时扩欧的点这里）

这就是扩欧模板了吧。。。

bx\equiv1\pmod{p}

等价于方程

bx-py=1

直接上模板好吧。

3.线性递推

参考zjp_shadow的逆元题解

用于求一连串数字的逆元。P3811

首先有：1^{-1}\equiv1\pmod{p}

不妨设p=k\times i + r(1 < r < i < p)

则有

k \times i + r \equiv0\pmod{p} \therefore k\times r^{-1} + i^{-1}\equiv0\pmod{p} \therefore i^{-1}\equiv-k\times r^{-1}\pmod{p} \therefore i^{-1}\equiv -\left\lfloor\dfrac{p}{i}\right\rfloor \times (p \mod i)^{-1}\pmod{p}

然后就可以线性时间求出逆元了


inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

 

完结撒花！！！