欧几里德算法（又称辗转相除法、GCD算法）应该是数论中最经典的算法了，同时也是初学一门语言时经典的练习题之一。

欧几里德算法

欧几里德算法的作用就是计算两个数的最大公约数，下面是它的C++语言实现：

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

gcd(a, b)就是计算a和b的最大公约数，很简单就可以改写成迭代形式，这里不再赘述。
而且这个算法的正确性也很显然，a和b的最大公约数m必然也是b和a % b的最大公约数，因为a % b == a - b * ⌊a / b⌋ ，由于a和b都能被m整数，所以a % b必然也能被m整除（⌊a / b⌋是a / b向下取整的意思）。

扩展欧几里德算法：

要是只介绍一个这样的欧几里德，也就太乏味了，所以，我们这里的主题是扩展欧几里德算法。
扩展欧几里德算法要解决一个什么样的问题呢？
a * x + b * y = d其中x和y是整数（可以为负），d是a和b的最大公约数。
扩展欧几里德算法的C++语言实现：

void exgcd(int a, int b, int &d, int &x, int &y)
{
    if(b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b, d, y, x);
        y -= a / b * x;
    }
}

扩展欧几里德算法和欧几里德算法的复杂度都是O(logN)的。

证明：

// TODO: 这里推理有点儿问题，待修改
这里最好反着推，首先看b == 0的情况，这时候d = a就是a和b的最大公约数，而且此时x = 1, y = 0，于是a * 1 + y * 0 = d是成立的。
然后会返回递归的上一层，注意这里exgcd(b, a % b, y, x)这里x和y的位置是调换的。
设k = ⌊a / b⌋ ，递归返回后已经满足：b * y + (a - k * b) * x = d。
我们需要得到a * x + b * y = d，这里的a * x相对(a - k * b) * y大了k * x，所以要在这个等式左面减去k * x，于是最后一步的y -= a / b * x也就清楚了。

继续深入...

我们已经求得了a * x + b * y = d的一组整数解，不难发现，d为gcd(a, b)或者gcd(a, b)的整数倍时，方程有解，否则无解。如果有解的话，方程有无穷多组解。
那么如何求出方程的其他解呢？
我们设a * x + b * y = a * x' + b * y' = d，x'和y'就是方程的另一组解。
移项后得到a * (x - x') = b * (y' - y)，然后在方程左右两边同时除以d，得到a' * (x - x') = b' * (y' - y)，此时a'和b'是互素的，那么若要等式成立，必然存在x - x'是b'的整数倍。
设x - x' = k * b'，计算得到y' - y = k * a'，所以x' = x - k * b', y' = y + k * a'。
于是得到以下结论：
若x和y是a * x + b * y = d的一组整数解，则方程的其他整数解都可以表示为(x - k * b', y + k * a')，这里a' = a / gcd(a, b)，b' = b / gcd(a, b)，k是任意整数。

标签: 算法, 数论