同余中的逆乘法逆元是连接CSP-J和CSP-S的重要概念理解它会让你的数论知识更成体系。下面我为你系统讲解“逆”是什么、怎么求、以及CSP-J/CSP-S中可能出现的典型例题。一、什么是乘法逆元1.1 从“倒数”说起1.2 举个具体例子二、逆元存在的条件重点核心定理a 在模 m 下存在乘法逆元 ⇔ gcd(a, m) 1a 和 m 互质为什么方程 ax≡1(modm)ax≡1(modm) 等价于 ax−my1ax−my1即 axmy1axmy1。根据裴蜀定理这个方程有整数解当且仅当 gcd(a, m) | 1即 gcd(a, m) 1。特例当模数 m 是质数 p 时只要 a 不是 p 的倍数就一定有逆元。判断练习amgcd(a,m)是否有逆元3101✅ 有2102❌ 无491✅ 有693❌ 无7131✅ 有三、求逆元的三种方法方法1枚举法适合小模数适用场景m 很小CSP-J级别步骤从 1 到 m-1 枚举 b检查 a×b≡1(modm)a×b≡1(modm)int inv(int a, int m) { for (int b 1; b m; b) { if ((a * b) % m 1) return b; } return -1; // 不存在逆元 }例题求 4 在模 9 下的逆元。枚举4×144×284×312≡34×416≡74×520≡24×624≡64×728≡1 ✓答案7方法2扩展欧几里得算法CSP-S要求原理求 axmy1axmy1 的一组整数解x 就是 a 的逆元。// 扩展欧几里得返回 gcd(a,b)同时求出 ax by gcd(a,b) 的一组解 int exgcd(int a, int b, int x, int y) { if (b 0) { x 1; y 0; return a; } int x1, y1; int g exgcd(b, a % b, x1, y1); x y1; y x1 - (a / b) * y1; return g; } // 求 a 在模 m 下的逆元要求 gcd(a,m)1 int modInv(int a, int m) { int x, y; int g exgcd(a, m, x, y); if (g ! 1) return -1; // 不存在逆元 return (x % m m) % m; // 保证结果为正 }方法3费马小定理模数为质数时// 用快速幂求 a^{p-2} mod p int modInv(int a, int p) { return quickPow(a, p-2, p); // p 必须为质数 }四、逆元的核心应用应用1解同余方程应用2模意义下的除法应用3组合数取模CSP-S重点五、CSP-J 典型例题概念判断型例题1存在性判断题目在模 8 的意义下下列哪个数存在乘法逆元A. 2 B. 3 C. 4 D. 6答案B解析存在逆元 ⇔ gcd(a,8)1gcd(2,8)2 ❌gcd(3,8)1 ✅gcd(4,8)4 ❌gcd(6,8)2 ❌选B。例题2同余方程题目同余方程 5x≡3(mod7)5x≡3(mod7) 的解是 A. 1 B. 2 C. 3 D. 4答案B解析5 在模 7 下的逆元是 35×315≡1x ≡ 3×3 9 ≡ 2 (mod 7)验证5×210≡3 ✓选B。例题3模运算变形题目已知 a≡2(mod5)a≡2(mod5)b≡3(mod5)b≡3(mod5)则 a×(mod5) 的值为 A. 1 B. 2 C. 3 D. 4答案D解析3 在模 5 下的逆元是 23×26≡1a ×≡ 2 × 2 4 (mod 5)选D。