数论——扩展欧几里得算法

扩展欧几里得算法

定义：

通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

应用：

求解线性同余方程，求逆元

算法原理描述

$(1)a{x}_i+b{y}_i=gcd(a,b)$
$(2)b{x}_{i-1}+(a\%b)y_{i-1}=gcd(b,a\%b)$
$(3)a\%b)x_{i-2}+[b\%(a\%b)]y_{i-2}=gcd(b,a\%b)$
$........$
$（n）d\ast 1+0=gcd(a,b)$
(1)、(2)式，（2）式可以转换成$a{y}_{i-1}+b(x_{i-1}-(a//b)y_{i-1})$，可以求得$x_i=y_{i-1}$,$y_i=x_{i-1}-(a//b)y_{i-1}$
同理（2）式转换为（1）式形式，相对于（3）式的关系也是一样的，可以通过递归实现

例题

模板题

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含两个整数 ai,bi。

输出格式
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的 xi,yi 均可。

数据范围
1≤n≤10^5,
1≤ai,bi≤2×10^9
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1

n = int(input())
def exgcd(a, b) :
	if b == 0 :
		return 1, 0
	x, y = exgcd(b, a % b)
	x, y = y, x - (a // b) * y
	return x, y, d
for i in range(n) :
	a, b = map(int, input().split())
	res = exgcd(a, b)
	print(res[0], res[1], end = " ")
	print()
1
2
3
4
5
6
7
8
9
10
11
12

求线性同余方程

给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 $a_i\times x_i\equiv b_i(mod{m}_i)$，如果无解则输出 impossible。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组数据 ai,bi,mi。

输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围
1≤n≤10^5,
1≤ai,bi,mi≤2×10^9
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3

思路讲解

$a\times x\equiv b(modm)$=>$ax+my=b$，则$gcd(a,m)|b$，通过扩展欧几里得算法$a{x}^{{}^{\prime }}+m{y}^{{}^{\prime }}=gcd(a,m)$可以求得 $a\ast x^{{}^{\prime }}\equiv gcd(a,m)(modm)$,中的x’由模的乘法运算知， $a\ast x^{{}^{\prime }}\ast (b//gcd(a,m))modm\equiv b(modm)$

n = int(input())

def exgcd(a, b) :
	if b == 0 :
		return 1, 0, a
	x, y, d = exgcd(b, a % b)
	return y, x - (a // b) * y, d

for i in range(n) :
	a, b, m = map(int, input().split())
	res = exgcd(a, m)
	if b % res[2] != 0 :
		print("impossible")
	else :
		print(res[0] * (b // res[2]) % m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

这篇关于欧几里得算法的讲解算是非常详细了，此外欧几里得算法对于求解逆元是非常有帮助的，相当于线性同余方程$a\times x\equiv b(modm)$，中b = 1的情况