BISHI74 【模板】非质模数下的乘法逆元

乘法逆元a−1≡x(modm)a^{-1} \equiv x \pmod ma−1≡x(modm)等价于求解线性同余方程：

ax≡1(modm) ⟹ ax+my=1ax \equiv 1 \pmod m \implies ax + my = 1ax≡1(modm)⟹ax+my=1

根据裴蜀定理，该方程有解的充要条件是gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1。
扩展欧几里得算法可以在计算gcd⁡(a,m)\gcd(a, m)gcd(a,m)的同时，求出一组整数(x,y)(x, y)(x,y)满足ax+my=gcd⁡(a,m)ax + my = \gcd(a, m)ax+my=gcd(a,m)。

思路

实现代码

privatestaticlongx;privatestaticlongy;publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取测试用例数量intT=Integer.parseInt(br.readLine().trim());// 处理每个测试用例for(inti=0;i<T;i++){String[]str=br.readLine().split("\\s+");longa=Long.parseLong(str[0]);longm=Long.parseLong(str[1]);exgcd(a,m);longans=(x%m+m)%m;out.println(ans);}// 清空输出缓冲区并关闭资源out.flush();out.close();br.close();}/** * 扩展欧几里得算法，用于求解形如 ax + by = gcd(a,b) 的方程 * 同时返回最大公约数和x、y的值 * * @param a 第一个参数 * @param b 第二个参数 * @return a和b的最大公约数 */privatestaticlongexgcd(longa,longb){// 当b为0时，递归结束，此时a就是最大公约数if(b==0){x=1;// x初始化为1y=0;// y初始化为0returna;}// 递归调用，计算b和a mod b的最大公约数longd=exgcd(b,a%b);// 通过递归结果更新x和y的值longtmp=x;x=y;y=tmp-(a/b)*y;// 返回最大公约数returnd;}