ACM 进阶学习第一课-同缺相关之欧几里得算法及其扩展（2）

ACM 进阶学习第一课----同余相关之欧几里得算法及其扩展（2）
最大公约数算法分析欧几里德算法伪代码while b>0
    do r←a%b
         a←b
         b←r
return a
算法分析：欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高
时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)
空间复杂度:O(1)
但是,对于大整数来说,取模运算非常耗时
Stein算法伪代码：Stein算法(假设0<=b<a):
r←0
while b>0
   do if a偶,b偶 then a←a>>1   b←b>>1   r←r+1
        else if a偶,b奇 then a←a>>1
        else if a奇,b偶 then b←b>>1
        else if a奇,b奇 then a←(a-b)>>1
        if a<b then 交换a,b
return a<<r
算法分析渐近时间,空间复杂度均与欧几里德算法相同
原理:gcd(ka,kb)=k*gcd(a,b)
最大特点:只有移位和加减法计算,避免了大整数的取模运算
代码：

  p = p1 + b/Gcd(a, b) * t  q = q1 - a/Gcd(a, b) * t(其中t为任意整数)  p 、q就是p * a+q * b = c的所有整数解。相关证明可参考：http://www.cnblogs.com/void/archive/2011/04/18/2020357.html 用扩展欧几里得算法解不定方程ax+by=c;代码如下：
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=1;i<d;i++)        printf("%d\n",(x0+i*(n/d))%n);    return true;}

（3）用欧几里德算法求模的逆元：
       同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解。
      在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。
      这时称求出的 x 为 a 的对模 n 乘法的逆元。
      对于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程
      ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。