GCD欧几里得算法&exGCD拓欧

定义#

即最大公约数, 若的最大公约数为,则记为：

即最小公倍数, 若的最小公倍数为,则记为： 即拓展欧几里得定理,用来在已知时,求解一组,使得。

性质#

1. 两个数的最大公约数乘以它们的最小公倍数就等于和本身的乘积。
   证明：
   设。根据最大公约数的定义,有。再根据最小公倍数的定义,有=于是。证毕。

求解#

1. 辗转相除法 用来求两个数的最大公约数,又称欧几里得算法,
   其原理就是：。
   原理的证明如下： 设,则。 设不是的因子,则不是的公因子。 设不是的因子,则不是的公因子。 代码实现如下：

   int GCD(int x,int y){
       return y==0? x:GCD(y,x%y);
   }
   //或者下面这个
   int GCD(int x,int y){
       while(y^=x^=y^=x%=y);return x;
   }

   cpp

   使用欧几里得算法求最大公约数的复杂度为。欧几里得算法是最常用的求最大公约数的方法。不过,因为高精度除法(取模)不容易实现,需要做高精度运算时,可考虑用更相减损术代替欧几里得算法。

2. 更相减损术
   ,有
   证明：
   根据最大公约数的定义,后者显然成立,我们主要证明前者。对于的任意公约数,因为,所以。因此也是的公约数。反之亦成立。故的公约数集合与的公约数集合相同。于是它们的最大公约数自然也相等。对于同理。
   证毕。

#

扩展欧几里德算法是用来在已知时,求解一组,使得。
因为 ,所以,这样它就将与的线性组合化简为与的线性组合。 根据前边的结论：和都在减小,当减小到时,就可以得出。然后递归回去就可以求出最终的p和q了。

int extended_gcd(int a，int b，int &x，int &y){
    int ret，tmp; 
    if (!b){
        x=1;
        y=0;
        return a;
    } 
    ret=extended_gcd(b，a % b，x，y); 
    tmp=x;
    x=y; 
    y=tmp-a / b * y;
    return ret; 
} 

一种更为高效简单的做法：

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b, a%b, y, x);
    y-=a/b*x;
    return d;
}