CSP-S 2024 第一轮 第9题：考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)

题目

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

选项

• A. 使用暴力法依次尝试
• B. 使用扩展欧几里得算法
• C. 使用快速幂法
• D. 使用线性筛法

答案

B

题解

答案：B. 使用扩展欧几里得算法。

要求 \(n\) 在模 \(m\) 意义下的逆元，就是求整数 \(x\)，使得 \[ nx\equiv 1\pmod m, \] 等价于寻找整数 \(x,y\)，满足 \[ nx+my=1. \]

扩展欧几里得算法可以求出 \[ nx+my=\gcd(n,m) \] 的一组整数解。因此：

• 若 \(\gcd(n,m)=1\)，逆元存在，取求出的 \(x\)，用 \((x\bmod m+m)\bmod m\) 归一化即可。
• 若 \(\gcd(n,m)\ne1\)，逆元不存在。

其他选项中，暴力法效率较低；快速幂常用的 \(n^{m-2}\bmod m\) 求逆元要求 \(m\) 为质数且 \(n\) 不是 \(m\) 的倍数，题目没有保证；线性筛法更适合批量计算特定范围内的逆元。因此选 B。