逆元 - Inverse element

做题做到要求分数求逆元，记录一下模板

• 数论
• 逆元

逆元

用快速幂就能求。

一般描述为：对一个不可约分数 ，输出整数 ，其中 是满足 的整数。

那么求 时可以通过 modInverseFastPower(q) 来计算。

const int mod = (int)1e9 + 7;
int qpow(int base, int x) {
  int sum = 1;
  while (x) {
    if (x & 1) {
      sum = (sum * base) % mod;
    }
    base = (base * base) % mod;
    x >>= 1;
  }
  return sum;
}
int modInverseFastPower(int a) { return qpow(a, mod - 2); }