此站用来记录个人的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
假设d是a,b的一个公约数,则有d|a, d|b,而r = a - kb,因此d|r
(备注:因为d是a,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赋值过程,这就是扩展欧几里德算法的精髓。