求解最大公约数 - 欧几里德算法

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

欧几里德算法

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

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

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

扩展欧几里德算法:

要是只介绍一个这样的欧几里德,也就太乏味了,所以,我们这里的主题是扩展欧几里德算法
扩展欧几里德算法要解决一个什么样的问题呢?
a * x + b * y = d其中xy是整数(可以为负),dab的最大公约数。
扩展欧几里德算法的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)的。

证明:

这里最好反着推,首先看b == 0的情况,这时候d = a就是ab的最大公约数,而且此时x = 1, y = 0,于是a * 1 + y * 0 = d是成立的。
然后会返回递归的上一层,注意这里exgcd(b, a % b, y, x)这里xy的位置是调换的。
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的一组整数解,不难发现,dgcd(a, b)或者gcd(a, b)的整数倍时,方程有解,否则无解。如果有解的话,方程有无穷多组解。
那么如何求出方程的其他解呢?
我们设a * x + b * y = a * x' + b * y' = dx'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'
于是得到以下结论:
xya * x + b * y = d的一组整数解,则方程的其他整数解都可以表示为(x - k * b', y + k * a'),这里a' = a / gcd(a, b)b' = b / gcd(a, b)k是任意整数。

标签: 算法, 数论

添加新评论