扩展欧几里得算法

扩展欧几里得算法

用于求ax+by=gcd（a, b）；

代码实现：

def ext_euclid(a, b):
     if b == 0:
         return 1, 0, a
     else:
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         x, y = y, (x - (a // b) * y)		#整除
         return x, y, q