乘法逆元

· · 算法·理论

乘法逆元

定义：

对于整数 a 和 m，m > 1，如果存在整数 x 满足：

a \times x \equiv 1 (\bmod m)

则称 x 是 a 在模 m 意义下的乘法逆元，记作 a^{-1}。

定理 1 ：a 在模 m 意义下有乘法逆元的充要条件是：

\gcd(a, m) = 1

即 a 与 m 互质。

::::info[证明]{open}

  1. 必要性：如果 \gcd(a,m) = d > 1，假设存在逆元 x 使得 a \times x \equiv 1 (\bmod m)，则 a \times x = k \times m + 1，由于 d 整除 a 和 m，所以 d 整除 1 矛盾。
  2. 充分性：如果 \gcd(a,m) =1，根据扩展欧几里得，那么存在 x,y 使得 a \times x + m \times y = 1，于是 a\times x \equiv 1 (\bmod m)，即 x 就是 a 的逆元。 ::::

求解逆元的方法

方法 1 ： 扩展欧几里得求解逆元

原理：把求解逆元的同余方程转化为不定方程求解。

优点：可以又判断误解的步骤，并且非常实用。

时间复杂度：O(\log n)。

方法 2 ：费马小定理

我们需要明确前提：仅当模数为质数且 a 与 p 互质。

如果 p 是质数，且 a 不是 p 的倍数，（即 \gcd(a,p) = 1），那么有：

a^{p - 1} \equiv 1(\bmod p)

转化一下可以发现：

)

所以 a 的逆元为 a^{p - 2}。

方法 3 : 线性递推求解逆元

如果我们需要求解 1 \sim n 在模质数 p 下的逆元，那么有一种线性递推方法可以求解。

设 i 的逆元为 inv_i。

则有：

inv_i = (p - \lfloor \frac{p}{i} \rfloor) \times inv_{p \bmod i} \bmod p

::::info[证明]{open}

令 p = k \times i + r，其中 k = \lfloor \frac{p}{i}\rfloor，r = p \bmod i。

在模 p 意义下：

p = k \times i + r \equiv 0 (\bmod p)

两边同乘 i^{-1}，r^{-1}：

k \times r^{-1} + i^{-1} \equiv 0 (\bmod p)

因此：

i^{-1} \equiv - k \times r^{-1} (\bmod p)

将 k = \lfloor \frac{p}{i}\rfloor，r = p \bmod i 代入，得证。 ::::

注意边界条件：inv_1 = 1。（因为 1 \times 1 \equiv 1 (\bmod p)）。

方法 4 : 阶乘逆元的线性求解

如果我们需要求解 1! \sim n! 的逆元，那么可以使用这种方法。

令 f_i 为 i! 的逆元，那么在已经使用费马小定理求出 f_n 的前提下，有：

f_i = f_{i + 1} \times (i + 1) \bmod p

::::info[证明]{open} 因为易得：

i! = \frac{(i + 1)!}{i + 1}

所以同时将两边取逆元，得：

(i!)^{-1} = [(i + 1)!]^{-1} \times (i + 1) \bmod p

得证。 ::::

例题

P1082

这是一道求逆元的模板题，发现数据范围非常大，且没有说一定互质，所以不能使用费马小定理，所以需要使用扩展欧几里得求解。

::::info[Code]

#include <bits/stdc++.h> 
using namespace std;
#define int long long
int T, a, b, c, x, y;
int exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int x1, y1;
  int d = exgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return d;
}
signed main() {
  cin >> a >> b;
  int d = exgcd(a, b, x, y);
  cout << ((x % b + b) % b ? (x % b + b) % b : b) << '\n';
  return 0;
}

::::

P3811

我们发现这道题的 n 达到了 3\times 10^{6}，所以我们不能使用费马小定理求解，所以使用第三种方法，线性求解逆元。

::::info[Code]

#include <bits/stdc++.h> 
using namespace std;
#define int long long
const int N = 3e6 + 5;
int n, p, inv[N];
void getinv() {
  inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = (p - p / i) * inv[p % i] % p;
}
signed main() { 
  cin >> n >> p;
  getinv();
  for (int i = 1; i <= n; i++) cout << inv[i] << '\n';
  return 0;
}

::::

P2265

题意非常简洁明了，直接说做法。

分析答案，因为只能向左或者向上，所以总共的步数为 n + m，所以我们需要在总步数中选取 n 不向左走，或者选择 m 步向上走，两种方法答案一样，所以答案为：\binom{n}{n+m}。

那么组合数的求解是基本功了，直接使用逆元算就完了。

::::info[Code]

#include <bits/stdc++.h> 
using namespace std;
#define int long long
const int N = 2e6 + 5, mod = 1e9 + 7;
int n, m, inv[N], infa[N];
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
int fac(int x) {
  int ans = 1;
  for (int i = 1; i <= x; i++) ans = ans * i % mod;
  return ans;
}
int C(int n, int m) {
  if (n < 0 || m < 0 || n < m) return 0;
  return fac(n) * qpow(fac(n - m), mod - 2) % mod * qpow(fac(m), mod - 2) % mod;
}
signed main() { 
  cin >> n >> m;
  cout << C(n + m, n) << '\n';
  return 0;
}

::::