欧几里得算法

Published: June 14, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 欧几里得算法
• 扩展欧几里得算法

欧几里得算法

要求两个数的最大公约数，我们可以利用欧几里得算法实现。

//要求a >= b >= 0
gcd(a, b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b)
}

先来讨论正确性，设$g$是$a$和$b$的最大公约数，那么$a\pmod b = a-kb=g(\frac{a}{g}-k\frac{b}{g})$，也是$g$的倍数。同理设$g'$是$b$和$a\pmod b$的最大公约数，那么有$a=a\pmod b + kb=g'(\frac{a\pmod b}{g'}+k\frac{b}{g'})$，因此$g'$也是$a$的因子。结合这两条性质可以直接推出$g=g'$。因此我们可以借助计算$b$和$a\pmod b$的最大公约数$g'$来得到$a$和$b$的最大公约数$g$。

之后来讨论时间复杂度，若$a\geq 2b$，那么$a\pmod b<\frac{a}{2}$。否则$a<2b$，则$a\pmod b\leq a - b<\frac{a}{2}$。因此不管哪种情况，较大的数在下次递归时都至少会减少一半。因此可以直接得出gcd递归调用的总次数为$O(\log ab)$，由于每次递归都是常数时间复杂度，因此这也就是我们要的时间复杂度。

由于$a$和$b$的最小公倍数等于$\frac{ab}{g}$，其中$g=gcd(a,b)$。因此我们可以直接推出最小公倍数算法：

//要求a >= b > 0
lcm(a, b){
    return a / gcd(a, b) * b; // 先除法后乘法的目的是防止乘法溢出
}

下面来了解以下欧几里得算法的性质。

欧几里得算法还有一个非常重要的特性，就是我们要计算$n$个数的最大公约数，实际时间复杂度应该是$O(n+\log_2M)$而不是$O(n\log_2M)$，其中$M$是这$n$个数中的最大值。

扩展欧几里得算法

扩展欧几里得算法可以帮助我们解决下面一类问题：

$$ax+by=c$$

其中$a$和$b$已知，且$c=gcd(a,b)$。要求我们找到一对合法的$(x,y)$。

当$b=0$的时候，我们一定有$a\cdot 1 + b\cdot 0=c$，接下来考虑如果我们已知$bx+(a-kb)y=c$，其中$k=\lfloor\frac{a}{b}\rfloor$。可以得出

$$ay+b(x-ky)=c$$

利用这个公式可以直接推出扩展欧几里得算法。

extgcd(a, b){
    if(b == 0){
        return {1, 0};
    }
    {x, y} = extgcd(b, a % b);
    return {y, x - a / b * y};
}

了解了扩展欧几里得原理后，我们可以利用它在模运算下计算$x^{-1}$。对于模运算下求逆，如果模的数是素数，我们可以用费马小定理计算，其时间复杂度是严格$\Theta(\log_2p)$，其中$p$是模数。但是如果我们用扩展欧几里得算法来求逆，那得到的是$O(\log_2p)$，即上界为此，但是实际上扩展欧几里得算法会快得多（实践中辗转次数非常少），并且扩欧不要求$p$是素数，只要求$p$和$x$互质。

扩欧还有一个非常重要的性质，就是我们可以发现算法中出现了乘法和减法运算，那么是否有可能在计算过程中出现数值溢出而导致结果错误呢？事实上这是不可能的，我们可以证明除非$b=0$的情况，有$(x,y)=(1,0)$，其余情况下都满足$|x|<b$且$|y|<a$。这里给一下证明：

考虑上面算法回退的时候，第一次满足$b>c$，则此时{x, y} = extgcd(b, a % b);得到的$x=0,y=1$，此时一定满足条件。现在假设该行返回的结果$(x,y)$满足条件$|x|<a-kb,|y|<b$，那么我们接下来证明return {y, x - a / b * y};这一行返回的结果也满足条件。很显然$y<b$是已经成立的了，因此我们只需要证明$|x - ky|<a$即可。

由于$bx+(a-kb)y=c<b$，因此一定有$x>0$且$y<0$或$x<0$且$y>0$中的一方成立。

• 如果$x>0$且$y<0$成立，则由于$y<0$此时$x-ky>0$一定成立，根据$x-ky<(a-kb)-ky<a-kb-kb=a$，因此有$|x - ky|<a$成立。
• 如果$x<0$且$y>0$成立，则由于$y>0$此时$x-ky<0$一定成立，根据$x-ky>-(a-kb)-ky>-a+kb-kb=-a$，因此有$|x - ky|<a$成立。

可以发现任意情况下都有$|x - ky|<a$。根据归纳法可以证明结论。

题目1：给定整数$a_1,\ldots,a_n$，判断是否存在一组整数变量$x_1,\ldots,x_n$，满足$\sum_{i=1}^na_ix_i=c$。

这实际上是扩欧的一个拓展，对于$n=2$的情况实际上就是扩欧。不难推出结果成立当且仅当$gcd(a_1,\ldots,a_n)$能整除$c$。

题目2：给定整数$a_1,\ldots,a_n$，判断是否存在一组非负整数变量$x_1,\ldots,x_n$，满足$\sum_{i=1}^na_ix_i=c$。

首先如果所有的整数都是同号，那么$c$必须同号。这个问题变成经典DP，时间复杂度为$O(nc)$。

如果$a_i$中存在负数$-q$和正数$p$，那么我们可以通过$-qp+(q-1)p=-p$来得到$-p$，同理可以得到$q$。同理这样我们可以认为$x_i$可以为负数，这与题目$1$相同。