【算法】数论逆元概念详解及其在Python中的应用

文章目录

前言

逆元（Modular Multiplicative Inverse）在模运算中是一个非常重要的概念，特别是在需要执行除法操作时。因为在模 p 的情况下，直接进行除法是不可行的，我们通常会使用乘以其逆元的方式来代替除法。

一、什么是逆元？

对于给定的整数 a 和模数 m，如果存在一个整数 b 满足：(a×b)%m=1
那么 b就被称为 a 在模 m 下的乘法逆元，记作 a^-1 或者 inv(a)。

二、逆元的存在条件

逆元存在的充分必要条件是 a 和 m 互质，即 gcd(a,m)=1。当 m 是质数时，所有1≤a<m 的 a 都有逆元。

三、 如何计算逆元？

1. 扩展欧几里得算法（Extended Euclidean Algorithm）

代码如下（示例）：

def extend_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    
    gcd, x1, y1 = extendgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return (gcd, x, y)

2. 使用费马小定理（Fermat’s Little Theorem）

当 m 是质数时，根据费马小定理，对于任意 a（a 不为m 的倍数），有：

可以使用快速幂算法来高效地计算这个值。

代码如下（示例）：

def mod_inverse_fermat(a, m):
    return pow(a, m - 2, m)

四、应用场景

逆元广泛应用于各种算法竞赛题目、密码学以及涉及模运算的数学问题中。例如，在计算组合数时，如果要除以某个数，可以通过乘以其逆元来实现。

示例：求排列数和组合数

下面是一个完整的示例，展示了如何预计算阶乘及其逆元，并用于计算排列组合A(n,k)和C(n,k)

code：

def pre(max_n, mod): # 预计算从 0 到 max_n 的阶乘及其逆元。
    f = [1] * (max_n + 1)  # factorials
    i_f = [1] * (max_n + 1) # inverse_factorials

    for i in range(1, max_n + 1):
        f[i] = f[i - 1] * i % mod

    # 计算 max_n 的逆元
    i_f[max_n] = pow(f[max_n], mod - 2, mod)

    # 反向计算其他阶乘的逆元
    for i in range(max_n, 0, -1):
        i_f[i - 1] = i_f[i] * i % mod

    return f, i_f # 两个列表 (factorials, inverse_factorials)，分别表示阶乘和阶乘的逆元。

# 计算组合数 C(n, k) = n!/( k!*(n-k)! )
def comb(n, k, f, i_f, mod): 
    if k > n or k < 0:
        return 0
    return (f[n] * i_f[k] % mod * i_f[n - k] % mod) % mod
    
 # 计算排列数 A(n, k) = n! / (n-k)!
def perm(n, k, f, i_f, mod): 
    if k > n or k < 0:
        return 0
    return (f[n] * i_f[n - k] % mod) % mod

当然，大多数时候我们只需要计算排列组合数，无需预处理出整个A/C(n,m)列表

code模板如下

mod = 10 ** 9 + 7

def C(n, m):
    p, q = 1, 1
    for i in range(1, m + 1):
        p = p * (n - i + 1) % mod
        q = q * i % mod
    return p * pow(q, mod - 2, mod) % mod

def A(n, m):
    p = 1
    for i in range(1, m + 1):
        p = p * (n - i + 1) % mod
    return p % mod

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢

作者：查理零世