Kuang Algorithm Engineer&Data Mining Engineer

欧几里得和扩展欧几里得

2017-12-17
Kuang
ACM

最近一直在用库函数__gcd(a,b)来求最大公约数,今天突然发现自己有点不记得gcd怎么写了,想着这些简单的数论知识还是得熟练掌握,不能仅仅调个函数了事,于是复习了一下gcd,顺便又复习了一下exgcd,在此做个记录。

1. 欧几里得算法

1.1 描述

欧几里得算法又称辗转相除法 ,是求最大公约数的算法。其主要是基于如下原理:两个整数的最大公约数等于其中较小的数和两数差的最大公约数 。因此,求两个数的最大公约数就可以根据该定理不断计算,直到出现0,此时另外一个数字就是最大公约数。

例: 求255和90的最大公约数

gcd(255,90) =gcd(255-2*90,90)=gcd(90-75,75)=gcd(75-5*15,15 )=15

因此255和90的最大公约数就是15

1.2 推论

欧几里得算法的一个重要推论是裴蜀定理,裴蜀定理的描述为:

关于未知数$x$和y的线性丢番图方程 有整数解的时候当且仅当m是a,b的最大公约数的倍数。

1.3 代码

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

2. 扩展欧几里得

2.1 裴蜀等式

上一章讲过,关于未知数$x$和y的线性丢番图方程 有整数解的时候当且仅当m是a,b的最大公约数的倍数。其中,关于未知数x和y的线性丢番图方程可称为裴蜀等式。裴蜀等式有解时必然有无穷多个整数解,每组解x、y都成为裴蜀数。

2.2 扩展欧几里得算法

扩展欧几里得算法的作用是在求a和b的最大公约数时,求得对应的裴蜀数x,y。当a是负数时,我们通常把问题转化为

扩展欧几里得的主要想法是收集辗转相除法过程中产生的式子,然后倒推回去,得到线性方程的解。

例如,求57x+31y=1的整数解,求57和31的最大公约数过程如下

26 = 57-31*1

5 = 31-26*1

1=26-5*5

得到57和31的最大公约数为1。

将这些式子倒回去,可得

1=26-(31-16*1)*5

1=26-(31-( (57-31)*1)*1)*5

1=57-31*1-(31-( (57-31)*1)*1)*5

1=6*57-31*11

得到x = 6 y = -11。

2.3 代码

假设已经求得了 的整数解 ,将

带入得到

而当b=0时则有

a*1+b*0 = a =gcd(a,b)

因此扩展欧几里得代码如下

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

Comments