ACM数论-欧几里得与拓展欧几里得算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。

基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。

递归版算法：

 int gcd(int a,int b)

 {

     if(b==)

         return a;

     return

         gcd(b,a%b);

 }

递归优化版：

 int gcd(int a,int b)

  {

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

  }

迭代版：

 int Gcd(int a, int b)

 {

     while(b != )

     {

     　　int r = b;

     　　b = a % b;

     　　a = r;

     }

     return a;

 }

扩展欧几里德算法

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

　　2，ab!=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;

　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

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

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

递归版算法：

 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）求解模的逆元；

用扩展欧几里得算法解不定方程ax+by=c：

 bool linear_equation(int a,int b,int c,int &x,int &y)

 {

     int d=exgcd(a,b,x,y);

     if(c%d)

         return false;

     int k=c/d;

     x*=k; y*=k;    //求得的只是其中一组解

     return true;

 }

求出解之间的间隔，那么就可以求出模的线性方程的解集：

 bool modular_linear_equation(int a,int b,int n)

 {

     int x,y,x0,i;

     int d=exgcd(a,n,x,y);

     if(b%d)

         return false;

     x0=x*(b/d)%n;   //特解

     for(i=;i<d;i++)

         printf("%d\n",(x0+i*(n/d))%n);

     return true;

 }

巴特西

ACM数论-欧几里得与拓展欧几里得算法

最新文章

热门文章