跳转至

乘法逆元

逆元简介

如果一个线性同余方程 ax \equiv 1 \pmod b ,则 x 称为 a \mod b 的逆元,记作 a^{-1}

如何求逆元

扩展欧几里得法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  ex_gcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return;
}

扩展欧几里得法和求解 线性同余方程 是一个原理,在这里不展开解释。

快速幂法:

这个要运用 费马小定理

p 为质数, a 为正整数,且 a p 互质,则 a^{p-1} \equiv 1 \pmod p

因为 ax \equiv 1 \pmod b

所以 ax \equiv a^{b-1} \pmod b (根据费马小定理);

所以 x \equiv a^{b-2} \pmod b

然后我们就可以用快速幂来求了。

代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#define ll long long
inline ll poW(ll a, ll b) {
  long long ans = 1;
  a %= p;
  while (b) {
    if (b & 1) ans = ((ans * a) % p + p) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return ans % p;
}

线性求逆元

但是如果要求的很多,以上两种方法就显得慢了,很有可能超时,所以下面来讲一下如何线性求逆元。

首先,很显然的 1^{-1} \equiv 1 \pmod p

然后,设 p=ki+j,j<i,1<i<p ,再放到 \mod p 意义下就会得到: ki+j \equiv 0 \pmod p

两边同时乘 i^{-1},j^{-1}

kj^{-1}+i^{-1} \equiv 0 \pmod p

i^{-1} \equiv -kj^{-1}+ \pmod p

i^{-1} \equiv -(\frac{p}{i}) (p \mod i)^{-1}

然后我们就可以推出逆元了,代码只有一行:

1
a[i] = -(p / i) * a[p % i];

但是,有些情况下要避免出现负数,所以我们要改改代码,让它只求正整数:

1
a[i] = (p - p / i) * a[p % i] % p;

这就是线性求逆元

逆元练习题

【模板】乘法逆元

同余方程

[AHOI2005] 洗牌

[SDOI2016] 排列计数


评论