扩展欧几里得算法

        本文探讨扩展欧几里得算法，这是一个基础而常用的数论算法。

        众所周知，欧几里得算法（辗转相除法）是求解两数最大公约数的算法，前文又认识到stein算法用于在高精度下代替欧几里得算法。扩展欧几里得算法又是做什么的呢？
        扩展欧几里得算法不仅可以求出两数（假如为a，b）的最大公因数，还可以求出方程$ax+by=gcd(a,b)$的一个特解。
        在过河的题后注解中，已经认识到了模线性方程解的性质，这里不再重复。下面探讨算法思想。
        考虑数15和36，它们的欧几里得算法过程如下：

$$36\div 15=2\cdots \cdots 6\\ 15\div6=2\cdots \cdots 3\\ 6\div 3=2\cdots \cdots 0\\ 3\div 0 =X$$

        所以最大公约数为3。
        容易发现整个过程中出现了4个算式，对于每一个式子中的被除数和除数，将其设为a、b（比如第一个式子中a=36，第二个中a=15），并设gcd(36，15)=g，考虑a和b的一组特解x₁、y₁，那么有：

$$ax_1+by_1=g$$

        将这个式子扩展下去。根据带余除法原理，可以把a写成如下形式：

$$a=kb+r,0\leq r<b$$

        r就是余数，显然有gcd(a，b)=gcd(b，r)。b和r组成了一个新的除式，设它们的特解为x₂、y₂，则有：

$$bx_2+ry_2=g$$

        于是：

$$ax_1+by_1=bx_2+ry_2$$

        代入a=kb+r，整理可得：

$$(kx_1+y_1)b+x_1r=x_2b+y_2r$$

        由于只需要求一个特解，不妨令b和r的系数分别相等，于是得到：

$$x_1=y_2\\ y_1=x_2-kx_1=x_2-(a/b)y_2$$

        注意这里的a/b表示整除。
        这个等式揭示了不同除式解的关系。我们的目标是求第一个算式（即对于被除数为36、除数为15的情况）的特解，而最后一个除式解显然为x=1，y=0，便可以通过这个递推关系得到原方程特解，并得到以下形式代码：

int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int t = exGcd(b, a % b, x, y);
    int x1 = y, y1 = x - a / b * y;
    x = x1, y = y1;
    return t;
}

        代码也可以简化为以下版本：

int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int t = exGcd(b, a % b, y, x);
    y-= a / b * x;
    return t;
}

        这样x和y就是方程的一个特解。