乘法逆元 $a^{-1} \equiv x \pmod m$ 等价于求解线性同余方程：
$ax \equiv 1 \pmod m \implies ax + my = 1$
根据裴蜀定理，该方程有解的充要条件是 $\gcd(a, m) = 1$。
扩展欧几里得算法可以在计算 $\gcd(a, m)$ 的同时，求出一组整数 $(x, y)$ 满足 $ax + my = \gcd(a, m)$。
思路
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
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;
}
|