逆元

定义

若p为素数， $abequiv 1(mod p)$ ,则称a与b在模p意义下互为逆元。

求法

1.用exgcd或者欧拉函数求方程 $ax + by = 1$ 的解，这样，我们便求到了逆元。至于exgcd是基本操作，不给代码了。

2.用费马小定理来进行求解。费马小定理是欧拉函数在p为质数的特殊情况，内容如下

$a^{^{p-1}}equiv 1(mod p)$

显然我们就可以得出 $a^{^{-1}} = a^{p-2}(mod p)$

我们用快速幂差不多也可以快速地得出答案。

3.若p是质数，那么1到p-1是都有逆元的。

我们可以用递推来求出这一阶段的所有逆元，这是非常有用的。

$i^{-1} = (p - left lfloor frac{p}{i} ight floor)(p\%i)^{-1} \% p$

至于证明...

在这里我来一段预处理阶乘的代码。其中也用到了递推求逆元。

//s[]阶乘，s1[]逆元
void jiecheng(){
    s[0] = s[1] = s1[0] = s1[1] = 1;
    for (int i = 2 ;i <= 100001;i ++){
        s[i] = 1ll * s[i - 1] * i % t;
        s1[i] = s1[t % i] * (t - t / i) % t;
    } 
    for (int i = 2;i <= 100001;i ++)
        s1[i] = 1ll * s1[i] * s1[i - 1] % t;
}

总结

逆元的应用是非常广的。有了逆元，我们可以在模意义下可以完成乘法。上图的代码可以求组合数，用到这一方法，中国剩余定理也需要逆元来做，因此，掌握逆元是比较重要的。