乘法逆元

概念讲解

什么是逆元？

如果 ax≡1(modm)ax \equiv 1 \pmod{m}，则 x 是 a 模 m 的逆元，记作 a−1a^{-1}。

作用

abmod  p=a×b−1mod  p\frac{a}{b} \mod p = a \times b^{-1} \mod p

求法

1. 扩展欧几里得

12345int inv(int a, int m) {
    int x, y;
    extgcd(a, m, x, y);
    return (x % m + m) % m;
}

条件：gcd⁡(a,m)=1\gcd(a, m) = 1

2. 费马小定理

如果 p 是质数：

a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod{p}

123int inv(int a, int p) {
    return quickPowerMod(a, p - 2, p);
}

条件：p 是质数

3. 线性递推

求 1~n 的逆元：

1234inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

考点分析

初赛考查方式

  1. 程序阅读： 逆元求解
  2. 编程题： 组合数取模

常见考点

  • 逆元求法
  • 费马小定理
  • 线性递推

例题精讲

例题 1：费马小定理

题目： 求 3 模 7 的逆元。

解答：

3−1≡37−2=35=243≡5(mod7)3^{-1} \equiv 3^{7-2} = 3^5 = 243 \equiv 5 \pmod{7}

验证：3 × 5 = 15 ≡ 1 (mod 7)

练习题

  1. 逆元的作用是什么？
查看答案

逆元的作用是将除法取模转化为乘法取模：

abmod  p=a×b−1mod  p\frac{a}{b} \mod p = a \times b^{-1} \mod p

在组合数取模、分数取模等问题中非常有用。

  1. 费马小定理的条件是什么？
查看答案

费马小定理的条件：

  1. p 是质数
  2. a 不是 p 的倍数（即 gcd⁡(a,p)=1\gcd(a, p) = 1）

结论：ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

所以：a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod{p}

  1. 线性递推的时间复杂度是多少？
查看答案

O(n)O(n)

1234inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

可以一次性求出 1~n 的所有逆元。

易错点

⚠️ 注意：

  1. 逆元存在条件：gcd(a, m) = 1
  2. 费马小定理要求 p 是质数
  3. 线性递推只能求 1~n 的逆元
  4. 注意取模