阿毛の次元

Amaok – 修合无人见,存心有天知。

GCD的几种实现方法

最简单的gcd算法:

int gcd(int x, int y)
{
     if(y == 0) return x;    
     if(x < y)      return gcd(y,x);    
     else        return gcd(y, x%y); 
} 

ACM中常用的gcd算法:

int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); } 

经过优化的gcd算法(分成奇偶两种情况):

int gcd(int x,int y )
{
    if(x < y) return gcd(y,x);  // x>y
    if( y == 0) return x;  // if y=0, x is GCD 
    else
    {
         if( !(x%2) )
         {                 
           if( !(y%2) )  //x,y both even
               return 2*gcd(x >> 1, y >> 1);    
          else      // x is even, y is odd
               return gcd(x >> 1, y );  
         }
          else 
         {
           if( !(y%2) )  // x is  odd,  y is even
               return gcd(x, y >> 1);
           else       // x, y both odd
               return gcd(y,x-y); 
         }
    }
}