题解 | 【模板】非质模数下的乘法逆元

import java.io.*;
import java.util.*;

public class Main {
    private static long x;
    private static long y;

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取测试用例数量
        int T = Integer.parseInt(br.readLine().trim());

        // 处理每个测试用例
        for (int i = 0; i < T; i++) {

            String[] str = br.readLine().split("\\s+");
            long a = Long.parseLong(str[0]);
            long m = Long.parseLong(str[1]);

            exgcd(a, m);
            long ans = (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的最大公约数
     */
    private static long exgcd(long a, long b) {

        // 当b为0时，递归结束，此时a就是最大公约数
        if (b == 0) {
            x = 1;    // x初始化为1
            y = 0;    // y初始化为0
            return a;
        }

        // 递归调用，计算b和a mod b的最大公约数
        long d = exgcd(b, a % b);
        // 通过递归结果更新x和y的值
        long tmp = x;
        x = y;
        y = tmp - (a / b) * y;

        // 返回最大公约数
        return d;
    }
}