费马小定理求逆元

CR450AF-锐龙追梦

2026-07-22 10:14:15

发布于：浙江

13阅读

0回复

0点赞

费马小定理是数论中的一个重要定理，在编程竞赛中常用于求乘法逆元。以下是详细解释：

一、定理内容
如果 p 是一个质数，且 a 不是 p 的倍数（即 a 和 p 互质），那么：

a^(p-1) ≡ 1 (mod p)

换句话说：a 的 p-1 次方除以 p 的余数等于 1。

二、推导乘法逆元
在模运算中，我们经常需要计算 a 除以 b 的余数（即 a × (1/b) mod p）。但模运算中不能直接做除法，需要用到乘法逆元。

乘法逆元的定义：
如果 b × x ≡ 1 (mod p)，那么 x 就是 b 在模 p 下的乘法逆元，记作 b^(-1)。

三、费马小定理求逆元
由费马小定理：b^(p-1) ≡ 1 (mod p)

变形：b × b^(p-2) ≡ 1 (mod p)

对比逆元定义：b × x ≡ 1 (mod p)

可得：x = b^(p-2) mod p

结论：b 的乘法逆元就是 b^(p-2) % p（要求 p 是质数，且 b 不被 p 整除）。

四、代码实现（快速幂）
求逆元需要计算 b^(p-2)，指数很大（例如 p=998244353 时，p-2≈10^9），需要用快速幂优化：

// 快速幂：计算 a^b % MOD
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;  // 如果当前二进制位是1，乘上a
        a = a * a % MOD;                  // a自乘
        b >>= 1;                          // 指数右移一位
    }
    return res;
}

// 求逆元：b^(MOD-2) % MOD
long long inv(long long b) {
    return qpow(b, MOD - 2);
}