python拓展欧几里得算法
时间: 2023-11-05 17:59:55 浏览: 44
拓展欧几里得算法是一种用于求解两个整数的最大公约数和乘法逆元的算法。如果两个整数a和b不互素,则拓展欧几里得算法的输出为None;如果a和b互素,则输出二者的乘法逆元。以下是Python实现拓展欧几里得算法的代码:
def extendGcd(m, b):
if m < b:
t = m
m = b
b = t
x1, x2, x3 = 1, 0, m
y1, y2, y3 = 0, 1, b
while True:
if y3 == 0:
return 'None'
break
elif y3 == 1:
return y2 % m
break
else:
Q = x3 // y3
t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
a = int(input())
b = int(input())
r = extendGcd(a, b)
print(r)
请注意,在使用这段代码之前,需要先提供两个整数a和b作为输入。然后,代码将输出a和b的乘法逆元。如果a和b不互素,则输出为None。
相关问题
python扩展欧几里得算法
扩展欧几里得算法是一种用于求解一元线性同余方程的算法,可以表示为ax ≡ b (mod n)。在Python中,我们可以用以下函数来实现扩展欧几里得算法:
```python
def extended_gcd(a, b):
if b == 0:
return 1, 0, a
else:
x, y, d = extended_gcd(b, a % b)
return y, x - (a // b) * y, d
def solve_linear_congruence(a, b, n):
x, y, d = extended_gcd(a, n)
if b % d == 0:
x0 = (x * (b // d)) % n
for i in range(d):
print("x ≡", (x0 + i * (n // d)) % n, "(mod", n, ")")
else:
print("无解")
```
在这段代码中,我们首先定义了一个`extended_gcd`函数,用于计算扩展欧几里得算法的结果。然后我们定义了一个`solve_linear_congruence`函数,用于解一元线性同余方程。这个函数会调用`extended_gcd`函数来得到结果,并根据情况输出方程的解或者无解情况。
通过这段代码,我们可以方便地在Python中使用扩展欧几里得算法来解决一元线性同余方程,这对于一些加密算法和数论问题来说是非常有用的。
python实现欧几里得算法
欧几里得算法(又称辗转相除法)是求两个数的最大公约数的算法。在Python中,可以使用递归或循环实现欧几里得算法。
递归实现:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
循环实现:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
两个实现方式的时间复杂度都是O(log n),其中n是a和b的最大值。