求逆元通常指的是在模运算中找到一个数，使得它与另一个数相乘后模给定的数等于1。以下是几种常见的求逆元的方法：
扩展欧几里得算法
原理：扩展欧几里得算法可以求解线性同余方程`ax + by = gcd（a, b）`，当`gcd（a, b） = 1`时，可以找到整数`x`和`y`，使得`ax + by = 1`，此时`x`就是`a`模`b`的逆元。
代码示例（C++）：
```cpp
ll exgcd（ll a, ll b, ll &x, ll &y） {
if （!b） { x = 1, y = 0； return a； }
ll d = exgcd（b, a % b, y, x）；
y -= （a / b） * x；
return d；
}
ll mod_inverse（ll a, ll m） {
ll x, y；
ll d = exgcd（a, m, x, y）；
return d == 1 ？ （m + x % m） % m : -1；
}
费马小定理
原理：如果`p`是素数，且`gcd（a, p） = 1`，则`a^（p-1） ≡ 1 （mod p）`，即`a^（p-2） ≡ 1/a （mod p）`，所以`a`的逆元是`a^（p-2） mod p`。代码示例（C++）：```cppll qpow（ll a, ll b, ll m） {
ll res = 1；
while （b > 0） {
if （b & 1） res = res * a % m；
a = a * a % m；
b >>= 1；
}
return res；
}
ll getinv（int a, int mod） {
return qpow（a, mod - 2, mod）；
}
递归求逆元
原理：递归地求解`x`使得`x * a ≡ 1 （mod m）`。
代码示例（C++）：
```cpp
ll inv（int x, int mod） {
return x == 1 ？ 1 : （mod - mod / x） * inv（mod % x, mod） % mod；
}
以上方法中，扩展欧几里得算法的时间复杂度为`O（log n）`，而费马小定理和递归求逆元的时间复杂度为`O（log mod）`。在实际应用中，可以根据具体情况选择合适的方法来求逆元。需要注意的是，当模数`m`为素数时，费马小定理通常更为高效。