CSP-S 提高级 · CSP 2024 提高级第一轮 第 9 题

考虑一个自然数 $n$ 以及一个模数 $m$，你需要计算 $n$ 的逆元（即 $n$ 在模 $m$ 意义下的乘法逆元）。下列哪种算法最为适合？（ ）

这题别一上来就套公式，先看清题干有没有给模数 m 是质数这个关键条件。没给就是坑，直接选通用的扩展欧几里得，快速幂和线性筛都要求 m 为质数，暴力法太慢，一眼就能排除。

最容易栽跟头的就是惯性思维，看到求逆元就下意识想快速幂（毕竟平时模 998244353 用得最多），或者把线性筛当成万能预处理工具。这题题干特意没提 m 是质数，命题人就是想看你是不是真的理解了不同算法的适用范围边界。还有同学会纠结暴力法，其实 O(m) 在竞赛里基本没戏，除非 m 极小，否则直接判错。

这道题考查的是数论中乘法逆元的求解算法选择，核心在于理解不同算法对模数性质的要求。

先说概念：乘法逆元是指对于整数 a 和模数 m，若存在 x 使得 ax ≡ 1 (mod m)，则 x 为 a 的逆元，前提是 gcd(a, m) = 1。扩展欧几里得算法就是解方程 ax + my = 1 的特解，不依赖 m 是否为质数；快速幂求逆元则是基于费马小定理 a^(m-2) ≡ a^(-1) (mod m)，这一定理成立的前提是 m 必须为质数；线性筛法通常用于批量求 1 到 n 的逆元，同样要求模数是质数。

命题人挖坑的点很明确：题目只给了自然数 n 和模数 m，完全没提 m 是质数。这时候如果选了 C 或 D，就是掉进了“默认模数是质数”的陷阱里。A 选项暴力枚举 O(m) 复杂度太高，竞赛里几乎不可能用，除非 m 特别小，但题目没说，不能假设。

思考过程很简单：拿到题先扫一眼条件，确认 m 的性质未知，那就必须选一个不依赖 m 为质数的通用解法。扩展欧几里得算法时间复杂度 O(log m)，既高效又通用，完美契合题意。所以选 B 毫无争议。

避坑方面，平时做题遇到模 998244353 或 10^9+7 这种质数模数，快速幂确实更顺手，代码短、常数小。但一旦题目没说模数性质，或者模数是个合数（比如 10^9+6），千万别再用快速幂，否则结果肯定错。线性筛同理，它本质是递推，也要求模数为质数才能正确计算。

从考频趋势看，数论算法在题库里共考过 36 题，覆盖 2009 到 2026 年，其中 2026 年高达 13 题，2024 年也有 1 题；同余与模运算考了 28 题，2024 年有 6 题，2025 年 8 题，2026 年 7 题，明显是近年高频考点。扩展欧几里得算法和乘法逆元这两个细分点，题库里各只考了 1 题，且都集中在 2024 年 CSP 提高级。这说明这类基础但易混淆的知识点，命题人喜欢用单选题来考察学生的审题能力和算法适用条件辨析，未来大概率还会在提高级甚至入门级继续出现类似陷阱题。

预测的话，既然 2024 年刚考过一次，且 2025、2026 年同余类题目持续高频，这类考“模数是否为质数”的辨析题应该还会以不同形式重现，比如给一个具体的合数模数让你选算法，或者让你判断快速幂是否可用。暂无足够依据预测具体年份，但可以确定的是，这类题不会轻易消失。