乘法逆元

给定正整数a，b，如果有 $ax\ \equiv \ 1\ (mod\ b)$​，且a与b互质，则称x的最小正整数解为a模b的逆元，（可以理解为倒数)。模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

如果一个线性同余方程$ax\ \equiv \ 1\ (mod\ b)$,则x称为a mod b的逆元

扩展欧几里得法

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

快速幂法

int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}