跳转至

乘法逆元

逆元简介

如果一个线性同余方程 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]排列计数

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论