The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

欧几里德算法及其扩展算法的迭代版本(转)

整除和最大公约数。

如果m能整除n,记m|n

对于不全为0的两个整数ab,能同时整除他们俩的最大整数为它们的最大公约数,记为gcd(a,b)。如果gcd(a,b)=1,则ab互质。

gcd(a,b)可用欧几里德算法:

a = q1 * b + r1

b = q2 * r1 + r2

r1 = q3 * r2 + r3

r2 = q4 * r3 + r4

……

rn-3 = qn-1 * rn-2 + rn-1

rn-2 = qn * rn-1 + rn => rn就是gcd

rn-1 = qn+1 * rn + 0

欧几里德算法非常好写。以pascal语言为例:

function gcd(a,b:longint):longint;

begin

if b=0 then gcd:=a

else gcd:=gcd(b,a mod b);

end;

线性方程ax+by=c的解法。

对于abax+byab的线性组合。这里xy可以是任何整数。

g=gcd(a,b),则g整除所有的ax+by。特别地,所有ax+by的取值中,最小的正值为g

因此,方程ax+by=c,仅当gcd(a,b)|c时有解。因此只考虑方程ax+by=gcd(a,b)的解法。

回忆上一章中讲的欧几里德算法,在第i步,我们有

ri-2 = qi * ri-1 + ri 。若ri+1=0,ri就是gcd

假设ri可表示为ab的线性组合(xi,yi),即ri=axi+byi,则有(xi,yi)=(xi-2,yi-2)-qi* (xi-1,yi-1)

初始时, 由于a=q1*b+r1,即r1=a-b*q1,由序列{Rn}的通项公式Rn=R(n-2)-R(n-1)*q1,我们可以把a看做r(-1),

b看做,r0,那么对应于表达式ri=a*xi+b*yi,r(-1)=a=a*1+b*0=(1,0),r0=b=a*0+b*1=(0,1);

即r-1=a=(1,0)r0=b=(0,1)。这样便可一步步推出rn=(xn,yn),即为原方程的一组解。

因此有如下定理:

ab为非零整数,g=gcd(a,b),则方程

ax+by=g 总可以通过欧几里德算法找出一组可行整解,记为(x1,y1)。它的通解可以表示为:

(x,y)=(x1+k*b/g , y1-k*a/g) ,其中k为任意整数。

竞赛中常用的欧几里德扩展算法采用的是倒推的方法,相比而言,本章提供的方法需要的变量稍多,常数稍大(只大了一点点)。但由于易于用迭代实现,而且实际测试中两种算法时间差别十分微小,因此本算法仍有应用价值。

posted on 2009-07-10 17:59 abilitytao 阅读(561) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理