核心概述
模逆（Modular Inverse）：给定整数 a 与模 m，若 gcd(a,m)=1，则存在唯一 x∈[0,m) 使 a·x ≡ 1 (mod m)。常用扩展欧几里得或在素数模下用费马小定理 a^{p−2} 求逆。
原文引述
Description: Compute modular inverse x of a modulo m (a·x≡1 mod m). Use extended Euclid for general m when gcd(a,m)=1, or fast exponentiation a^{p−2} when m is prime. Time: exgcd O(log m); powmod O(log m) multiplications Status: tested
展开阐述
-
函数/接口（据实现）
- ll inv_exgcd(ll a, ll m)：返回 a 在模 m 下的逆；若 gcd(a,m)≠1 则按约定返回 −1（或抛出无解）。
- ll inv_prime(ll a, ll p)：当 p 为素数且 a%p≠0 时，返回 a^{p−2} mod p。
- vector
inv_prefix(ll n, ll p)：预处理 1..n 在素数模 p 下的逆，O(n)。
-
核心方法
- 扩展欧几里得（通用模）：
- 求 g,x,y 使 a·x + m·y = g = gcd(a,m)。若 g≠1 则无逆。
- 否则 inverse ≡ x mod m（规范到 [0,m)）。
- 费马小定理（素数模）：
- 若 p 素数且 a 与 p 互质，则 a^{p−1}≡1 (mod p)，故 inv ≡ a^{p−2} (mod p)。
- 使用快速幂 powmod 计算。
- 线性预处理（素数模）：
- inv[1]=1；对 i=2..n：inv[i]=(p − p/i) * inv[p%i] mod p。整体 O(n)。
- 扩展欧几里得（通用模）：
-
输出语义
- 返回值为 a 在模 m（或 p）下的逆元，位于 [0,m)。
- 若不存在逆元（gcd(a,m)≠1），按接口约定返回 −1/抛出错误。
-
复杂度
- inv_exgcd：O(log m)。
- inv_prime：O(log p) 次模乘。
- 批量预处理：O(n)。
-
使用与注意
- 规范化输入：先将 a 按 m 取模，确保 0≤a<m。
- 溢出：中间乘法用 128 位或见090-数论-长整型模乘；powmod 见091-数论-模幂。
- 非互质无逆：在组合数、解同余等应用中需先判 gcd(a,m)=1。
- 批量逆（乘积法）：可用前后缀乘法 O(n) 计算一组数的逆（固定模）以降常数。