【模板】非质模数下的乘法逆元时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定正整数对( a , m ) (a,m)(a,m)求乘法逆元a − 1 m o d m a^{−1} \mod ma−1modm。输入描述第一行输入测试组数T ( 1 ≦ T ≦ 10 4 ) T(1≦T≦10^4)T(1≦T≦104)。接下来T TT行每行输入两个整数a , m ( 1 ≦ a m ≦ 10 9 ) a,m(1≦am≦10^9)a,m(1≦am≦109)。需要特别注意的是数据不保证m mm为质数输出描述对于每组测试用例输出一行一个正整数表示表达式a − 1 m o d m a^{−1} \mod ma−1modm的值。示例1输入1 2 3输出2解题思路本题是通用模数下乘法逆元的模板题由于模数不保证为质数无法使用费马小定理采用扩展欧几里得算法求解线性同余方程判断逆元是否存在并计算结果。逆元存在性判定乘法逆元的定义为若整数x xx满足a ⋅ x ≡ 1 ( m o d m ) a \cdot x \equiv 1 \pmod{m}a⋅x≡1(modm)则称x xx为a aa在模m mm下的逆元。该式等价于线性丢番图方程a ⋅ x m ⋅ k 1 a \cdot x m \cdot k 1a⋅xm⋅k1。根据贝祖定理方程有解当且仅当gcd ⁡ ( a , m ) 1 \gcd(a, m) 1gcd(a,m)1即a aa与m mm互质若不互质则逆元不存在。扩展欧几里得算法在普通欧几里得求最大公约数的基础上扩展算法可同步求出方程a ⋅ x b ⋅ y gcd ⁡ ( a , b ) a \cdot x b \cdot y \gcd(a,b)a⋅xb⋅ygcd(a,b)的一组整数解递归边界当b 0 b 0b0时最大公约数为a aa对应解x 1 , y 0 x1,\ y0x1,y0。递归回溯已知gcd ⁡ ( b , a % b ) \gcd(b, a\%b)gcd(b,a%b)的解( x 1 , y 1 ) (x_1, y_1)(x1​,y1​)通过恒等变形推导当前层的解由b ⋅ x 1 ( a % b ) ⋅ y 1 gcd ⁡ b \cdot x_1 (a\%b) \cdot y_1 \gcdb⋅x1​(a%b)⋅y1​gcd代入a % b a − ⌊ a / b ⌋ ⋅ b a\%b a - \lfloor a/b \rfloor \cdot ba%ba−⌊a/b⌋⋅b整理得a ⋅ y 1 b ⋅ ( x 1 − ⌊ a / b ⌋ ⋅ y 1 ) gcd ⁡ a \cdot y_1 b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) \gcda⋅y1​b⋅(x1​−⌊a/b⌋⋅y1​)gcd因此当前解为x y 1 x y_1xy1​y x 1 − ⌊ a / b ⌋ ⋅ y 1 y x_1 - \lfloor a/b \rfloor \cdot y_1yx1​−⌊a/b⌋⋅y1​。结果调整若gcd ⁡ ( a , m ) ≠ 1 \gcd(a,m) \neq 1gcd(a,m)1逆元不存在若存在求出的x xx可能为负数通过(x % m m) % m将其调整为[ 0 , m − 1 ] [0, m-1][0,m−1]范围内的正整数即为最终的乘法逆元。算法单次时间复杂度为O ( log ⁡ min ⁡ ( a , m ) ) O(\log \min(a,m))O(logmin(a,m))可轻松应对万级测试数据。总结核心逻辑将逆元问题转化为线性同余方程求解通过扩展欧几里得算法计算解与最大公约数判断互质性后输出对应结果。关键操作扩展欧几里得递归求解、互质性判定、负数解转正取模。效率保障对数级时间复杂度单组测试运算量极低万级数据无运行压力。代码简要说明扩展欧几里得函数egcd递归实现返回a与b的最大公约数通过引用参数传回方程a x b y gcd ⁡ axby\gcdaxbygcd的一组整数解x、y。单组求解函数sol读取a和m调用扩展欧几里得算法得到最大公约数与解。若最大公约数不等于1输出-1表示逆元不存在。若逆元存在对解x执行两次取模调整为正整数输出最终逆元。主函数读取测试组数T循环调用求解函数关闭同步流加速输入输出适配万级数据的IO效率要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llegcd(ll a,ll b,llx,lly){if(b0){x1;y0;returna;}ll x1,y1;ll gegcd(b,a%b,x1,y1);xy1;yx1-a/b*y1;returng;}voidsol(){ll a,m;cinam;ll x,y;ll gegcd(a,m,x,y);if(g!1){cout-1\n;return;}ll ans(x%mm)%m;coutans\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;cinT;while(T--)sol();return0;}