风灵无畏OI

此站用来记录个人的OI成长史,以后会将个人做的每道题的解题报告发到此站上来,希望大家喜欢!(如有讲得不好的地方请大家指出,我会加以改进。当然也有可能传上来一点乱七八糟的东西)
注:转载文章请标上原址,毕竟码字很辛苦!谢谢!

欧几里得算法(未完成版)

以下内容部分来自度娘,另一部分来自百度百科。

https://baike.baidu.com/item/扩展欧几里德算法

【介绍】

       扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足贝祖等式: ax+by = gc

d(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程

组中。

【欧几里得算法】

一、概述

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖下面的定理:

gcd函数就是用来求(a,b)的最大公约数的。

gcd函数的基本性质

       gcd( a , b )=gcd( b , a ) = gcd( -a , b )=gcd( |a| , |b| )

二、公式表述

gcd(a,b)=gcd(b,a mod b)

证明:

    a可以表示成a = kb + r,则r = a mod b

    假设da,b的一个公约数,则有d|a, d|b,r = a - kb,因此d|r

  (备注:因为da,b的一个公约数,所以我们将a换成 y * d,把b换成 x * d,则可以得到r=y*d-k*x*d,变为r=(y-k*x)*d,所以d | r)(可能是我自己太蠢了吧)

    因此d( b , a mod b)的公约数 

    假设d( b , a mod b)的公约数,则

    d | b , d |r ,但是a = kb +r(如上,我们可以把b和r换一下,则可以得出)

    因此d也是(a,b)的公约数 

    因此(a,b)(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

【C++代码实现】

   int gcd(int a,int b){

    return b?gcd(b,a%b):a;

  }

【pascal代码实现】

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

begin

    if b=0 then exit(a);

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

end;

【扩展算法】

       对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然

存在整数对 x,y ,使得 gcd(a,b)=ax+by。

【C++代码实现】   

int gcd(int a,int b,int &x,int &y){

    if (b==0){

        x=1,y=0;

        return a;

    }

    int q=gcd(b,a%b,y,x);

    y-=a/b*x;

    return q;

}

【pascal代码实现】

function gcd(a,b:longint; var x,y:longint):longint;

var t:longint;

begin

    if b=0 then

        begin

            x:=1; y:=0;

            exit(a);

        end;

    gcd:=gcd(b,a mod b,y,x);

    y:=y-(a div b)*x;

end;

求解 x,y的方法的理解

   设 a>b

   1   显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;

   2   a>b>0 时

   设 ax1+ by1= gcd ( a , b );

        bx2 + ( a mod b )y2 = gcd ( b , a mod b );

   根据朴素的欧几里德原理有 gcd ( a , b ) = gcd ( b , a mod b );

   则: ax1 + by1 = bx2 + ( a mod b )y2;

   即: ax1 + by1 = bx2 + ( a - [ a / b ] * b )y2 = ay2 + bx2 - [ a / b ] * by2;

   也就是 ax1 + by1 = ay2 + b( x2 - [ a / b ] * y2);

   根据恒等定理得:x1= y2;  y1 = x2 - [ a / b ] * y2;

   这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.

   上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax+by = Gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

把这个实现和Gcd的递归实现相比,发现多了下面的x,y赋值过程,这就是扩展欧几里德算法的精髓。





评论

© 风灵无畏OI | Powered by LOFTER