学习链接:http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
先来学习一下什么是欧几里得算法:
欧几里得原理是:两个整数a ,b的公约数等于b ,a%b这两个数的公约数。即gcd(a,b)=gcd(b,a%b),他们的任何公约数都是相同的,所以他们的最大公约数也是相同的。
那么结合任何数和0的最大公约数都是他自己,就可以得出最大公约数的求解算法了。
int gcd(int a, int b)
{
if(b==)
return a;
else
return (b,a%b);
}
下面是拓展欧几里得算法:
基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。
证明:要证明这个式子成立,就是要找出整数对x,y。我们用递归的思想去寻找x,y。
1.显然当b=0时,gcd(a,b)=a,x = 1,y = 0;
2.ab!=0时,
假设:ax1+by1 = gcd(a,b);
bx2+(a % b)y2 = gcd(b,a%b);
又因为gcd(a,b)=gcd(b,a%b),所以有
ax1 +by1 = bx2+(a%b)y2;
以此类推:ax1 +by1 = bx2+(a%b)y2 = ……=#xn +(*%#)yn;
由此可见当*%#==0时,就可以知道xn,yn,以及#,*的值,这时如果在知道xn,yn和x(n-1),y(n-1)之间的递推关系就可以求出x1,y1了。
求递推关系:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;
证明的递推代码如下,也就是求x,y的代码:
int exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;
y=;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
我觉得这个代码写的还是挺吊的,至少以现在我的水平来看;嗯,要加到递归学习中去。非递归代码也放在这儿了:
int exgcd(int m,int n,int &x,int &y)
{
int x1,y1,x0,y0;
x0=; y0=;
x1=; y1=;
x=; y=;
int r=m%n;
int q=(m-r)/n;
while(r)
{
x=x0-q*x1; y=y0-q*y1;
x0=x1; y0=y1;
x1=x; y1=y;
m=n; n=r; r=m%n;
q=(m-r)/n;
}
return n;
}
下面讲一下应用:欧几里得算法主要有三个方面的应用:
1.求解不定方程;
2.求解模线性方程;
3.求解模的逆元;
(1)使用扩展欧几里德算法解决不定方程的办法:(来源:http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html)
对于不定整数方程pa+qb=c,若 c mod Gcd(p, q)=0,则该方程存在整数解,否则不存在整数解。
上面已经列出找一个整数解的方法,在找到p * a+q * b = Gcd(p, q)的一组解p0,q0后,p * a+q * b = Gcd(p, q)的其他整数解满足:
p = p0 + b/Gcd(p, q) * t
q = q0 - a/Gcd(p, q) * t(其中t为任意整数)
至于pa+qb=c的整数解,只需将p * a+q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。
在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后,应该是得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b)),
p * a+q * b = c的其他整数解满足: