求解逆元有如下几种方式：
1. 如果 mod 为 素数，那么可以使用费马小定理+快速幂求解
2. 如果 gcd(a,mod)==1 其中，a为求逆元素，并且满足前面的等式保证a存在逆元。 那么可以使用 扩展欧几里得
3. 递推法快速打表求解多个逆元， 要求 mod 必须为奇质数
4. 如果 mod 不为素数，那么可以使用通用解法，这里不详细讲（因为我也不会
下面讲解1，2，3方法
方法一：（如果 mod 为 素数，那么可以使用费马小定理+快速幂求解）
1. 费马小定理
如果 gcd(a,p) == 1， 并且 p 为素数，那么就有
公式变形：
所以：求解 a 的逆元，就是求解
2. 代码：求 a 在 mod 下的乘法逆元
1 //求 m^n % k 2 ll quick_power(ll m, ll n, ll k){ 3 ll ans = 1; 4 m %= k; 5 while(n){ 6 if(n & 1) 7 ans = ans * m % k; 8 n >>= 1; 9 m = m * m % k; 10 } 11 return ans; 12 } 13 14 ll inverse_quick_pow(ll a, ll mod){ 15 return quick_power(a,mod-2,mod); 16 }