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); } [/cc] ACM中常用的gcd算法： [cc] 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);
}
}
}