欧几里得算法与扩展算法相关内容

推荐博客 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

欧几里得算法求最大公约数（辗转相除）

定理 gcd( m , n )=gcd ( n , m mod n ) ( m>n 且 m mod n 不为0)

最小公倍数记为lcm( m , n )，显然lcm( m , n )=m*n / gcd( m , n )

对于正整数k,有性质 lcm( km , kn)=k*gcd( m , n )

欧几里得算法

ll gcd(ll a,ll b) 
{ 
    return b?gcd(b,a%b):a;
}

欧几里得算法递归实现

1 int gcd(int m,int n)
2 {
3     if(n<m)gcd(n,m);
4     if(n==0)return m;
5     else return gcd(n,m%n);
6 }

由欧几里得算法得知如果gcd( m , n )= 1,则m,n互素

扩展欧几里得算法

扩展欧几里得算法：对于不完全为0的非负整数a,b,gcd(a,b)表示a,b的最大公约数d,则存在整数对x,y,使得gcd(a,b)=ax+by。

定理：对于不定整数方程ax+by=c,若c mod gcd(a,b)=0(记为(a,b)|c,或d|c),则该方程存在整数解，否则不存在整数解。

证明：设 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，所以递归可以结束。

扩展欧几里得递归代码

 1 int exgcd(int a,int b,int &x,int &y)   //&引用符号，修改x,y,函数返回的是a,b的最大公约数
 2 {
 3     if(b==0)
 4     {
 5         x=1;                            
 6         y=0; 
 7         return a;
 8     }
 9     int r=exgcd(b,a%b,x,y);            //递归下去
10     int temp=x;
11     x=y;
12     y=temp-a/b*y;
13     return r;
14 }