时间复杂度T(n)：O(log2n);
空间复杂度S(n)：O(n);
Advantages：
1、 时间复杂度不高，和普通欧几里得一样；
2、 代码简洁，易于编写；
3、 适用于数学问题求解；
Disadvantages：
1、 代码难以理解，需要学会数学公式的推理；
2、 用途不广，适用范围较小；
注意：
1、 适用于ax + by = gcd(a, b)的方程求解；
2、 一般化为ax + by = 1，也就是将a，b除以最小公约数;
3、 计算过程中，若要交换两数，则最后需进行判断哪个是答案；
4、 若求取得是ax + by = gcd(a, b) *k, 最后的答案也要乘k；
算法实现：
1） 普通欧几里得
gcd(a, b) = gcd(b, a % b), 不断迭代，直到b = 0，a就是最大公约数
2） 拓展欧几里得
ax + bx = gcd(a, b) = gcd(b, a % b), 不断迭代，直到b = 0，x = 1, y = 0;
普通欧几里得：
适用题型：
求两个数a,b的最大公约数gcd(a,b)
输入：a，b两个整数
输出：a，b的最大公约数
Source：
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
拓展欧几里得：
适用题型：
青蛙的约会【扩展欧几里得，浙江省选2002】
题目背景
POJ1061
ZJOI2002
TJOI2002
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 0 度处为原点，由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x，青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。
输入格式
输入有多组数据，每组输入数据只包括一行 5 个整数 x，y，m，n，L。
其中 x≠y＜2,000,000,000；0＜m,n＜2,000,000,000；0＜L＜2,100,000,000 。
输出格式
对每组数据，输出一行，为一个整数，即碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“Impossible” 。
样例数据 1
输入
1 2 3 4 5
输出
4
Source:
/* created by scarlyw */ #include <cstdio> #include <string> #include <algorithm> #include <cmath> #include <iostream> #include <cstring> #include <cctype> inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template<class T> inline void R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = ((x << 2) + x << 1) + (c ^ '0'); if (iosig) x = -x; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void write_char(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template<class T> inline void W(T x) { static int buf[30], cnt; if (x == 0) write_char('0'); else { if (x < 0) write_char('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) write_char(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } long long x, y, m, n, l, t, a, b, c; long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } inline void ext_gcd(long long a, long long b, long long &x, long long &y) { b ? (ext_gcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0); } int main() { R(x), R(y), R(m), R(n), R(l); a = m - n, b = l, c = y - x, t = gcd(a, b); if (c % t) std::cout << "Impossible", exit(0); a /= t, b /= t, c /= t, ext_gcd(a, b, x, y); if (b < 0) b = -b; x *= c, std::cout << (x % b + b) % b; return 0; }
算法分析：
此题其实就是扩展欧几里德算法——求解不定方程，线性同余方程。
设跳跃s步后两青蛙相遇， (x+ m * s)为原坐标为x的青蛙在相遇处的坐标值；(y +n * s) 为原坐标为y的青蛙在相遇处的坐标值。两个青蛙如果在第一圈相遇，相遇处坐标相同，则坐标差为0；如果在第二圈相遇，则相遇坐标差为2 * L，……，所以相遇处坐标差为k * L(k= 0, 1, 2....)。 则必满足以下等式： (x + m * s) - (y + n * s) = k * L (k = 0, 1, 2....) 稍微变一下形得： (n - m) * s + k * L = x - y 令a = n- m, b = L, c = x - y, 即 a * s + b * k = c 只要上式存在关于s和k的整数解，则两青蛙能相遇，否则不能。所以，c一定是gcd(a ,b)的倍数；看到这里就很容易想到扩展欧几里得。
算法实现：
1） 推出公式：(n - m) * s + k * L =x - y；
2） 将公式简化为a * s + b * k = c; 求出gcd(a, b) = t，若c % t == 0则可进行下一步计算，否则不可能实现。
3） a, b, c分别除以t，得到a0 * s + b0 * k = c0;(a0 = a / t; b0 = b / t; c0 = c / t)因为此时的a0, b0最大公约数一定为1；所以可以求出a0 *s0 + b0 * k0 = 1的整数解s0, y0，s = s0* c0 = s0 * c / t; k = k0 * c0 = k0 * c / t; 从而求出需要的解s；
4） 因为最后的s一定是大于0且小于l的值，所以最后通过 (s % l + l)% l 保证取值范围；
