SkyWT

我们的征途是星辰大海。

欧几里德算法与拓展欧几里德算法略解

OI学习数论

欧几里德算法(Euclidean algorithm)又叫做辗转相除法,用于求最大公约数。这个算法已经十分常见了。扩展欧几里德算法(Extended Euclidean algorithm)是欧几里德算法的扩展(废话……),这个算法在解不定方程的时候十分常见。

本文中 (a,b) 或者 gcd(a,b) 表示 a、b 的最大公约数; a|b 表示 a 整除 b。

本文隶属⌈ 数论学习系列 ⌋。

欧几里德算法/辗转相除法

在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。、
——维基百科

代码

在我们日常的题目里辗转相除法已经十分常见了,最大公约数(Greatest Common Divisor)缩写为GCD,所以函数名就是gcd(当然扩欧的函数名就是exgcd)。其主要代码段是这样的:

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

以上代码其实可以写成以下这样:

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

原理和证明

辗转相除法的原理是什么呢?显然gcd(a,b)的作用是求出a、b的最大公约数(在数学语言里直接用(a,b)表示a、b的最大公约数)。如果b为0就返回a的值不难理解,这说明已经找到了最大公约数a。关键在于:

$$(a,b) = (b,a \bmod b)$$

关于这个等式证明如下:

首先根据:

$$a=kb+r (a,b,k,r \in N^+,r < b)$$

可以化为:

$$r=a-kb=a \bmod b$$

假设 $d$ 是 $a,b$ 的一个公约数,则 $d \mid a , d \mid b$。所以:

$$d \mid a-kb \iff d \mid a \bmod b$$

即:

$$(a,b) \iff (b,a \bmod b)$$

通俗点说,$d$ 是 $a,b$ 两个数的公约数,又是 $b,a \bmod b$ 的公约数,所以 $a,b$ 的公约数集与 $b,a \bmod b$ 的公约数集相同,它们的最大公约数必然也相同。

扩展欧几里德算法

扩展欧几里德算法(Extended Euclidean algorithm)就像是欧几里德算法的逆运算。

用途

主要有以下几种用途:

  1. 求解不定方程;
  2. 求解模线性方程(线性同余方程);
  3. 求解模的逆元。

求解不定方程的方法

个人觉得求解不定方程这个用途比较常见。可以方便地用来解这样的不定方程(传说中的裴蜀等式):

$$ax+by=c$$

其实我们要解这个补不定方程,就要先解出 $ax+by=gcd(a,b)$。基于这两个事实:

  1. 给予二个整数 $a,b$,必存在整数 $x,y$,使得 $ax+by=gcd(a,b)$。

  2. 对于方程 $ax+by=c$,当且仅当 $(a,b)|c$ 时这个方程有解。

容易证明,如果我们求出方程 $ax+by=(a,b)$ 的一组特殊解 $x_0,y_0$,则最后方程解为:

$$ \begin{cases} x= x_0 +k \ast \frac b {(a,b)} \\ y= y_0 -k \ast \frac a {(a,b)} \end{cases} $$

那么如何“求出方程 $ax+by=(a,b)$ 的一组特殊解”?这时候拓展欧几里德算法就派上用场了。

求解线性同余方程的方法

对于以下方程:

$$ax≡b \pmod n$$

如何求解这样的方程呢?其实这个方程可以看成:

$$ax+ny=b (x,y \in Z)$$

(注意 $n$ 一般是负数)这样就可以用不定方程的方法求解了!

代码

int exgcd(int a,int b,int &x,int &y){ //x、y变量用来传递求得的特殊解
    if(b==0){ //判断递归边界,b=0说明到底了
        x=1;y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y),t=x; //先递归把之前的都做完
    x=y;y=t-a/b*y;
    return r;
}

原理

先举个例子吧,求不定方程 $1234x+4321y=1$ 的整数解。 首先求 $(1234,4321)$,过程如下:

$$(1234,4321)=(1234,619)=(615,619)=(615,4)=(3,4)=(3,1)=(0,1)=1$$

我们得到了 $(1234,4321)=1$。接下来用扩展欧几里德算法可以倒着推回去:

$$ \begin{aligned} 1&=1- \underline 0 \\ &= 1-(3-3 \ast 1) = -3-2 \ast \underline 1 \\ &= (4-2 \ast 3)-3 = 4-3 \ast \underline 3 \\ &= 4 - (615-153 \ast 4) = 154 \ast \underline 4 - 615 \\ &= 154 \ast (619 - 615) - 615 = 154 \ast 619 - 155 \ast \underline {615} \\ &= 154 \ast 619 - 155 \ast (1234 - 619) = 309 \ast \underline {619} - 155 \ast 1234 \\ &= 309 \ast (4321-3 \ast 1234) -155 \ast 1234 = 309 \ast \underline {4321} -1082 \ast \underline {1234} \end{aligned} $$

所以这一组特解就是:$x=-1082, y=309$。按照这样的思路,前面的程序就不难理解了。先递归求 $x$ 和 $y$,再把 $x$ “复原”。

证明不会



Related posts

欧拉函数、费马小定理与欧拉定理略解
发表评论
撰写评论