gcd和ex

gcd就是欧几里得算法，可以快速的求出俩个数的最大公因数，进而也可以求其最大公倍数（俩数之积除以最大公因数），比较简单直接看代码就好了,一般用递归版，简短精简，敲得快，但如果数剧奇葩，怕溢出，那就用递推版的。

递归版：

int gcd(int a,int b)

{ if(b==0)

return a;

return gcd(b,a%b);

}

递推版：

int gcd(int a,int b)

{ int r=a%b

while(r>0)

{ a=b;

b=r;

r=a%b; }

return b;

}

ex_gcd就是扩展欧几里得算法，解这个方程：ax+by=d 。也就是ax+by=gcd（a，b）。若要方程有解，则d=k*gcd（a,b）。是吧.

所以这个函数就是解的这个方程ax+by=gcd(a,b),而最后给解扩大k倍,使d=k*gcd(a,b)就看题意了。

int ex_gcd(int a,int b,int &x,int &y)

{ if(b==0)

{ x=1,y=0;

return a: }

int r=ex_gcd(b,a%b,x,y);

int t=x;

x=y; //解这个方程根据数学推导: x,y表示第一次递归时的值，x1,y1表示第二次递归时的值。那么 y=t-a/b*y; gcd(a,b)==gcd(b,a%b)，同时都代入原方程，有ax+by==b*x1+(a%b)*y1。将右边变形一下 b*x1+(a%b)*y1==b*x1+(a-(a/b)*b)*y1==a*y1+b*(x1-(a/b)*y1)，最终得到ax+by==a*y1+b*(x1-(a/b)*y1)

return r; 于是才有这个递归通式：x=y1;y=x1-a/b*y1

}

最后函数返回的r是a,b的最大公因数，这应该没问题吧，x,y分别存储函数的一组解。

x=x*(d/r);

y=y*(d/r);//或y=(d-ax)/b;

通常让求x的最小正整数解那么x=(x%(d/r)+d/r)%(d/r). y=(d-ax)/b.

扩展欧几里得用的比较多，各种应用题可以列这个方程解，还有逆元，求a对m的逆元，就是解方程ax+my=1的解（我们已经知道 (a*b)%m=(a%m*b%m)%m 那么如果求(a*b/c)%m则应该怎么化解，这时候就要求c的逆元，原式=(a%m*b%m*c~)%m，其中c~是c的逆元）

待续……

巴特西

gcd和ex_gcd

最新文章

热门文章