强化阶段（第 3 - 4 个月）：数学进阶之费马小定理在模逆元计算中的应用及快速幂求逆元

在 CSP - J 备考的强化阶段（第 3 - 4 个月），数学部分的进阶知识至关重要，其中费马小定理就是一个关键要点。

一、费马小定理的定义

费马小定理指出：若$p$为质数，$a$与$p$互质，则$a^{(p - 1)} \equiv 1\ mod\ p$。

二、费马小定理在模逆元计算中的应用

当我们需要计算$a$关于模$p$的逆元时，即求$x$使得$a \times x \equiv 1\ mod\ p$，根据费马小定理，因为$p$是质数且$a$与$p$互质，所以$a^{(p - 1)} \equiv 1\ mod\ p$。等式两边同时乘以$a^{-1}$，得到$a^{(p - 2)} \times a \times a^{-1} \equiv a^{-1}\ mod\ p$，即$a^{(p - 2)} \equiv a^{-1}\ mod\ p$。所以，$a$关于模$p$的逆元就是$a^{(p - 2)}\ mod\ p$。

三、快速幂求逆元的代码实现

以下是用 C++实现的快速幂求逆元的代码示例：

#include <iostream>
using namespace std;

typedef long long LL;

// 快速幂函数
LL qmi(LL a, LL b, LL p) {
    LL res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    LL a, p;
    cin >> a >> p;
    // 计算 a 关于模 p 的逆元
    LL inv = qmi(a, p - 2, p);
    cout << inv << endl;
    return 0;
}

在上述代码中，qmi函数实现了快速幂运算。通过调用qmi(a, p - 2, p)，即可得到$a$关于模$p$的逆元。

总之，在 CSP - J 备考的强化阶段，深入理解和掌握费马小定理及其在模逆元计算中的应用，并能熟练运用代码实现快速幂求逆元，对于提高数学解题能力，应对考试中的相关题目具有重要意义。希望同学们通过不断的练习和总结，熟练掌握这一知识点，在考试中取得优异成绩。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！