逆元求解方法详解：扩展欧几里得算法、快速幂、线性筛

逆元是指在模意义下，某个整数'a' 对于模数'm' 的逆元'b'，满足 (a * b) mod m = 1。在数论中，逆元是一种非常重要的概念，可以用来解决很多数学问题，如线性同余方程、最大公约数等等。

下面介绍几种求逆元的方法：

扩展欧几里得算法可以求出'a' 和 'm' 的最大公约数'gcd'，如果'gcd'=1，则说明'a' 和 'm' 互质，此时可以用扩展欧几里得算法求出'a' 对于 'm' 的逆元 'b'。具体步骤如下：

1）使用欧几里得算法求出'a' 和 'm' 的最大公约数'gcd'，同时也求出了'gcd' 的一组解'x' 和 'y'，满足 ax + my = gcd；

2）如果'gcd'=1，则说明'a' 和 'm' 互质，此时'b'=x mod m 就是'a' 对于 'm' 的逆元。

快速幂求逆元是一种比较简单的方法，具体步骤如下：

1）求出 a^(m-2) mod m，即为'a' 对于 'm' 的逆元。

2）根据费马小定理，如果'a' 和 'm' 互质，则 a^(m-1) mod m=1，因此 a^(m-2)mod m 就是'a' 对于 'm' 的逆元。

逆元线性筛是一种比较高效的方法，可以在 O(n) 的时间复杂度内求出 1~n 的所有数对于模数 'm' 的逆元。具体步骤如下：

1）先求出 1 的逆元 b[1]=1；

2）从 2 开始，依次求出 2~n 的逆元 b[i]，如果 'i' 和 'm' 互质，则 b[i]=(m-m/i)*b[m%i]%m，否则 b[i]=0。

最后，需要注意的是，在求逆元的时候，如果模数 'm' 不是质数，则可能存在没有逆元的情况，因此需要先判断 'm' 是否为质数。