最简单的gcd算法：
[cc]
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); }
[/cc]
经过优化的gcd算法(分成奇偶两种情况)：
[cc]
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);
}
}
}
[/cc]