扩展欧几里德算法

提到扩展欧几里德算法,先简要介绍下欧几里德算法,又称辗转相除法,用于计算两个整数a和b的最大公约数(Greatest Common Divisor(GCD))。扩展欧几里德算法

求解a和b的最大公约数中,a可以表示为kb+r,则r =a mod b,假设d是a和b的一个公约数,则有d|a,d|b,r = a - kb,因此d|r(因为d是a的约数,又是b的约数,所以也是他们的多项式的约数),所以d是(b,a mod b)的公约数。所以在这不断代换中,a 必然>b,每次将a换成b,b换成amod b, a ,b 不断减小。直到b为0时,此时a为他们的最大公约数。

扩展欧几里德算法
1 int euclid(int a,int b)   
2 {   
3       if (b==0)
4           return a;   
5       else  
6           return euclid(b,a%b);   
7 } 
View Code

而扩展欧几里德算法是用来求解已知a,b,求一组x,y使得a * x + b * y =Gcd(a,b)(这个解一定存在,数论定理)

因为Gcd(a,b)=Gcd(b,a%b),所以a * x + b * y = Gcd(a,b) = Gcd(b,a%b)。得b * x + (a%b)*y = b * x + (a - a/b*b)*y,这里的((a - a/b*b)*y)不难得出,之前是a%b。现在我想得到这个数,怎么来呢。首先a/b,得到一个整数,在a!=b的情况下,这个整数再乘以b之后是不等于a的。所以余数就是这里的差值。即a - a/b*b。如果a==b,那么Gcd==a==b。继续,b * x + (a%b)*y = b * x + (a - a/b*b)*y。展开得b*x + a*y - a/b*b*y,合并得a*y + b*(x-a/b*y).这样,因为a,b都在减小,当b=0时,可以得出x=1,y=0,此时递归回去可以求出x,y。

扩展欧几里德算法
 1 int extended_gcd(int a, int b, int &x, int &y) 
 2 {
 3     int ret, tmp; 
 4     if (!b) 
 5     {
 6         x = 1;
 7         y = 0;
 8         return a;  
 9     } 
10         ret = extended_gcd(b, a % b,x, y); 
11     tmp = x;
12     x = y; 
13     y = tmp - a / b * y;
14     return ret; 
15 } 
16     
View Code

 对于方程a * x + b * y=c,该方程等价于a*c ≡ c(mod b);有整数解的充要条件是 c % gcd(a,b)==0。(定理)

所以方程 a*x+b*y=n;我们可以先用扩展欧几里德算法求出一组x0,y0。即 a * x0 + b * y0 = Gcd(a,b);

然后两边同时除以Gcd(a,b) ,再乘以n。这样就得到了方程   :a * x0 * n / Gcd(a,b) + b * y0 * n / Gcd(a,b) =n;从而求出一个解

通过扩展欧几里德求的是ax + by = Gcd(a, b)的解,令解为(x0, y0),代入原方程,得:ax0 + by0 = Gcd(a, b),
如果要求ax + by = c = Gcd(a, b)*c',可以将上式代入,得:                                                        
ax + by = c = (ax0 + by0)c',则x = x0c', y = y0c', c' = c / Gcd(a,b)
这里的(x, y)只是这个方程的其中一组解,x的通解为 { x0c' + k*b/Gcd(a, b) | k为任意整数 },y的通解可以通过x通解的代入得出

若gcd(a,b)=1,即a、b互质,且x0,y0为a*x+b*y=n的一组解,则该方程的任一解可表示为:x=x0+b*t,y=y0-a*t;且对任一整数t,皆成立。
这样我们就可以求出方程的所有解了,但实际问题中,我们往往被要求去求最小整数解,所以我们就可以将一个特解x。令t=b/gcd(a,b)=1,特解x=(x%t+t)%t

扩展欧几里德算法

poj题目链接:

青蛙的约会   、 C Looooops   、The Balance  、Business Center  、 Comfort

上一篇:数字图像处理学习——(一)双线性差值算法


下一篇:js var 以及 let 的差异