2025-10-27-逆元基础知识与应用

参考资料

前言

在算法竞赛和密码学中，我们经常会遇到”模运算下的除法”问题。由于模运算的特殊性，我们不能直接进行除法运算，这时就需要用到逆元的概念。本文将从最基础的概念讲起，逐步深入到逆元与线性代数的联系，最后通过一道实战例题来巩固理解。

一、什么是逆元？

简单来说，逆元就是能让运算结果”回到原点”的那个数。

1.1 加法逆元（最容易理解）

  • 比如 5 的加法逆元是 -5，因为 5 + (-5) = 0
  • 就像你向东走5步，再向西走5步，就回到原地了
  • 规律：一个数的加法逆元就是它的相反数

1.2 乘法逆元

  • 比如 5 的乘法逆元是 1/5，因为 5 × (1/5) = 1
  • 就像把东西放大5倍后，再缩小到原来的1/5，就恢复原样了
  • 规律：一个数的乘法逆元就是它的倒数

1.3 模运算中的逆元（重点！）

这是编程和密码学中最常用的概念。

例子：在模7的世界里，3的逆元是5，因为：

3 × 5 = 15
15 mod 7 = 1

可以理解为：在一个”只有7个数字(0-6)的时钟”上，什么数乘以3能回到1？答案是5。

数学定义：若 a × x ≡ 1 (mod m)，则称 x 是 a 在模 m 意义下的乘法逆元，记作 a⁻¹。

二、逆元的应用场景

2.1 密码学

RSA加密算法的核心就是模逆元：

  • 加密：密文 = 明文^e mod n
  • 解密：明文 = 密文^d mod n
  • 其中 d 是 e 的模逆元

2.2 编程竞赛/算法题

求解除法取模问题：

// 计算 (a/b) mod p
// 转化为 a × b^(-1) mod p
// (因为直接除法取模会有精度问题)

2.3 分数运算（模意义下）

  • 在模运算中不能直接除法
  • 需要先求逆元，再相乘

2.4 线性方程求解

解方程 ax ≡ b (mod m)：

  • 需要求 a 的逆元 a^(-1)
  • 则 x = a^(-1) × b (mod m)

2.5 区块链/比特币

椭圆曲线密码学(ECC)大量使用模逆元运算

三、如何求逆元？

3.1 扩展欧几里得算法

最通用的方法：

  • 当 gcd(a, m) = 1 时，a 在模 m 意义下才存在逆元
  • 用扩展欧几里得算法可以快速找到这个逆元
// 扩展欧几里得算法
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 求逆元
ll inv(ll a, ll m) {
    ll x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}

3.2 快速幂方法（当模数是质数p）

根据费马小定理：a^(p-1) ≡ 1 (mod p)

所以：a的逆元 = a^(p-2) mod p

// 快速幂求逆元
ll power(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 求逆元（模数为质数）
ll inv(ll a, ll p) {
    return power(a, p - 2, p);
}

四、逆元与逆矩阵：数学思想的统一

4.1 核心类比关系

数的乘法 矩阵乘法
单位元是 1 单位元是 单位矩阵 I
a × a⁻¹ = 1 A × A⁻¹ = I
0 没有逆元 行列式为0的矩阵没有逆
非零数都有逆 满秩矩阵才有逆

4.2 都是”撤销操作”

数字层面:
  ×5 → ×(1/5) → 回到原点
  
矩阵层面:
  ×A → ×A⁻¹ → 回到原点
  
比如: 向量旋转30° → 旋转-30° → 回到原位置

4.3 存在性条件类似

数的逆元：

  • 普通除法: 分母不能为0
  • 模运算: gcd(a, m) = 1

矩阵的逆：

  • 行列式 det(A) ≠ 0
  • 矩阵必须是”满秩”的（列向量线性无关）

可以理解为：都要求”信息无损失”

  • 乘以0会丢失信息 → 无法恢复
  • 矩阵降维会丢失信息 → 无法恢复

4.4 群论视角：统一的数学框架

逆元和逆矩阵都是**群论(Group Theory)**中”逆元”的不同实例：

群的类型 元素 运算 单位元 逆元
实数乘法群 非零实数 × 1 1/a
模p乘法群 {1,2,…,p-1} ×(mod p) 1 a⁻¹ mod p
一般线性群GL(n) 可逆矩阵 矩阵乘法 I A⁻¹

关键洞察：1×1矩阵的逆就是数的倒数！

A = [5]
A⁻¹ = [1/5]
[5] × [1/5] = [1]

所以数的逆元可以看作是矩阵求逆在一维空间的特例！

五、实战例题：抢红包期望问题

5.1 题目描述

有一个软件的抢红包系统是这样设计的：假如现在红包里面还有 w 元，那么你抢红包能抢到的钱就是 [0,w] 等概率均匀随机出的一个实数 x。

现在有个人发了一个 w 元的红包，有 n 个人来抢。那么请问第 k 个人期望抢到多少钱？输出答案对 10^9+7 取模后的结果。

输入格式：

  • 一行三个整数 w, n, k (0≤w≤10^9, 0≤k≤n≤10^18)

输出格式：

  • 一行一个整数，表示第 k 个人期望抢到的钱数对 10^9+7 取模后的结果

示例：

输入：2 1 1
输出：1

5.2 问题分析

核心思路：每次到下一个人的时候，对应的期望都会变成原来的一半。

  • 第1个人：期望抢到 w/2
  • 第2个人：期望抢到 w/4 = w/(2^2)
  • 第3个人：期望抢到 w/8 = w/(2^3)
  • 第k个人：期望抢到 w/(2^k)

但是在模运算中，我们不能直接除以 2^k，需要使用乘法逆元：

w / (2^k) mod p  
=  w × (2^k)^(-1) mod p
=  w × (2^(-1))^k mod p

5.3 完整代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

// 快速幂：计算 base^exp % mod
ll power(ll base, ll exp) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) 
            res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll w, n, k;
    cin >> w >> n >> k;

    // 计算 2 在模 mod 意义下的乘法逆元
    // 根据费马小定理：2^(-1) = 2^(mod-2) mod mod
    ll inv2 = power(2, mod - 2);

    // 计算 (2^k) 的模逆元，即 (2的模逆元)^k
    ll inv2_k = power(inv2, k);

    // 期望 = w × (2^k 的模逆元) % mod
    ll ans = (w * inv2_k) % mod;

    cout << ans << endl;

    return 0;
}

5.4 代码关键点解析

  1. 使用费马小定理求逆元：

    • 由于 10^9+7 是质数
    • 所以 2^(-1) ≡ 2^(10^9+5) (mod 10^9+7)

  2. 巧妙处理大指数：

    • 不是直接计算 (2^k)^(-1)
    • 而是先算 2^(-1)，再求其 k 次方
    • 避免了计算超大的 2^k（k最大可达10^18）

  3. 快速幂优化：

    • 时间复杂度从 O(k) 降到 O(log k)
    • 对于 k=10^18 的情况至关重要

六、总结

逆元是现代算法和密码学中的核心概念，它：

  1. 在模运算中实现除法运算
  2. 与线性代数中的逆矩阵本质相同，都是群论中”逆元”概念的具体体现
  3. 求解方法：扩展欧几里得算法（通用）或快速幂+费马小定理（质数模）
  4. 广泛应用于：密码学、算法竞赛、区块链、图形学等领域

相关阅读推荐：