最大公约数问题

Posted on | In | |
Words count in article: 722 | Reading time ≈ 3

求两个正整数的最大公约数Greatest Common Divisor,GCD。

如果两个正整数都很大，有什么简单的算法？

例如求1 100 100 210 001 和 120 200 021 的最大公约数

解法一：

辗转相除法

假设用f(x,y)表示x,y的最大公约数，取k = x/y, b = x%y, 则x = ky + b， 如果一个数能够同时整除x和y，则必能同时整除b和y，而能同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的。

则有f(x,y) = f(y, x%y) (x >= y > 0)

1
2
3
4
int gcd(int x, int y)
{
    return (!y)? x:gcd(y, x%y);
}

解法二：

对于大整数而言，取模运算（其中用到除法）是非常昂贵的开销，有没有办法能不用取模运算？

采用类似前面辗转相除法的分析，如果一个数能够同时整除x和y，则必能同时整除x-y和y；而能够同时整除x-y和y的数也必能同时整除x和y，即x和y的公约数与x-y和y的公约数是相同的，其最大公约数也是相同的，即f(x,y) = f(x-y, y), 那么就可以不再需要进行大整数的取模运算，而转换成简单得多的大整数的减法。

在实际操作中，如果x < y, 可以先交换(x, y)，从而避免求一个正数和一个负数的最大公约数，一直迭代下去，知道其中一个数为0

1
2
3
4
5
6
7
8
9
BigInt gcd(BigInt x, BigInt y)
{
    if(x < y)
        return gcd(y, x);
    if(y == 0)
        return x;
    else
        return gcd(x-y, y);
}

代码中BigInt是自己实现的一个大整数类。

这个算法免去了大整数触发的繁琐，但是同样有不足之处，最大的瓶颈就是迭代的次数比之前多了很多。

解法三：

能否结合解法一和解法二，得到一个更佳的算法

对于y 和x 来说， 如果y = k*y1, x = k*x1。 那么有f(y, x) = k*f(y1, x1)。

另外，如果x = p x1, 假设p是素数，并且y%p！=0（即y不能被p整除），那么f(x, y) = f(px1, y) = f(x1, y)

因此：最简单的方法是，2是一个素数，同时对于二进制表示的大整数而言，可以很容易地将除以2和乘以2地运算转化为移位运算，从而避免大整数触发，由此就可以利用2来进行分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BigInt gcd(BigInt x, BigInt y)
{
    if(x < y)
        return gcd(y, x);
    if(y == 0)
        return x;
    else
    {
        if(IsEven(x))
        {
            if(IsEven(y))
                return (gcd(x >> 1, y >> 1) << 1);
            else
                return gcd(x >> 1, y);
        }
        else
        {
            if(IsEven(y))
                return gcd(x, y >> 1);
            else
                return gcd(y, x-y);
        }
    }
}
Donate? comment?