欧几里得算法

对于任意整数$a,b\in \mathbb{Z}$，欧几里得算法可用于求解其最大公约数$d=gcd(a,b)$。

首先，对于任意

拓展的欧几里得算法更进一步可以求得$s,t\in \mathbb{Z}$，使得$as+bt=d$。

拓展的欧几里得算法复杂度为$O(n^2)$，其n是a和b中最大的比特位数。？？