在数论中，如果逆元 - 图1 ，我们就说 逆元 - 图2 和 逆元 - 图3 在模 逆元 - 图4 意义下互为乘法逆元，记作 逆元 - 图5 。

逆元有什么用呢？我们常常遇到一些题目要求结果对一个大质数 逆元 - 图6 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以你可以处处取模来避免溢出。 但遇到除法时，就比较麻烦——因为处处取模和最后取模的结果是不一样的。 为了解决模意义下的除法问题，我们引入了逆元。 逆元 - 图7 其实可以看做模 逆元 - 图8 意义下的 逆元 - 图9 ，那么在模 逆元 - 图10 意义下， 逆元 - 图11 就可以变形为 逆元 - 图12 。

求逆元

求逆元共有三种方法：

  1. 拓展欧几里得
  2. 费马小定理
  3. 线性递推

    拓展欧几里得

    其实这篇文章里的那道例题就是了 拓展欧几里得
    必须要最后的公约数等于 1，即a和p 两个数互质才能求出逆元
    1. ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧
    2. {
    3.  if (b == 0)
    4.  {
    5.      x = 1;
    6.      y = 0;
    7.      return a;
    8.  }
    9.  ll d = exgcd(b, a % b, y, x);
    10.  y -= (a / b) * x;
    11.  return d;
    12. }
    13. ll inv(ll a, ll p)
    14. {
    15.  ll x, y;
    16.  if (exgcd(a, p, x, y) != 1) // 无解的情形
    17.      return -1;
    18.  return (x % p + p) % p;
    19. }

    费马小定理

    费马小定理是数论里的重要定理，叙述如下：

    若 逆元 - 图13 是质数，且 逆元 - 图14 ，则有 逆元 - 图15

从逆元的定义推导，可得 逆元 - 图16 ，于是有 逆元 - 图17

  1. inline ll qpow(ll a, ll n, ll p)// 快速幂 (a^n)%p
  2. {
  3.     ll ans = 1;
  4.     while (n)
  5.     {
  6.         if (n & 1)
  7.             ans = ans % p * a % p;
  8.         a = a % p * a % p;
  9.         n >>= 1;
  10.     }
  11.     return ans;
  12. }
  13. inline ll inv(ll a, ll p)//求逆元
  14. {
  15.     return qpow(a, p - 2, p);
  16. }

线性递推

还没学，先不写了。