zoj 4712 Modular Inverse 逆元 扩展欧几里得

缘起

【1】中我们已经给出了扩展欧几里得算法. 本文将介绍扩展欧几里得算法的一个应用——求逆元. 而且找到了求逆元的题目 zoj 4712 Modular Inverse

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
所谓求逆元是指,对于a,b两个整数(皆可正可负),求x使得ax模b为1(则x亦可能为负)

【输入】
多样例，第一行是样例数，每个样例包含两个正整数 0 < a ≤ 1000 and 0 < b ≤ 1000.

【输出】
对每个样例，输出最小的正整数解x, 如果这样的x不存在，打印 Not Exist

【样例输入】
3
3 11
4 12
5 13

【样例输出】
4
Not Exist
8

【限制】
Time Limit: 2 Seconds
Memory Limit: 65536 KB

逆元等价于

1
2
3
4
ax-1=by, 即
ax+b*(-y) = 1 即
ax+by=1(y和-y没有任何区别)
现在要球最小的正整数解x, 这不就是【1】中讲的东西吗?
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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int extgcd(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	int ans = extgcd(b,a%b, x,y),t;
	t = x,x=y,y=t-a/b*y;
	return ans;
}


int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t,a,b,x,y;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &a, &b);
		if (b==1) // 这里需要特判一下,在这里WA了一次
		{
			puts("1");
			continue;
		}
		int gcd = extgcd(a,b,x,y); // ax+by=1
		if (gcd!=1)
		{
			puts("Not Exist");
		}
		else
		{
			if (b>0)
			{
				while(x<0)x+=b;
				while(x>b)x-=b;
			}
			else
			{
				while(x<0)x-=b;
				while(x>-b)x+=b;
			}
			printf("%d\n", x);
		}
	}
	return 0;
}

ac情况

Status Accepted
Memory 184kB
Length 687
Lang C++ (g++ 4.7.2)
Submitted 2019-08-17 16:47:28
Shared
RemoteRunId 4657151

参考

【1】https://yfsyfs.github.io/2019/08/17/poj-1061-%E9%9D%92%E8%9B%99%E7%9A%84%E7%BA%A6%E4%BC%9A-%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97-%E6%9C%80%E5%B0%8F%E6%AD%A3%E6%95%B4%E6%95%B0%E8%A7%A3/#more