最大公约数

辗转相除法

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

但是取模运算的开销很大，可以考虑使用x-y替代，因为x,y,x-y一定具有相同的最大公约数。

int gcd2(int x,int y){
    if(x<y)
        return gcd2(y,x);
    if(y==0)
        return x;
    else
        return gcd2(y,x-y);
}

编程之美2.7节又提供了两种方法结合。

gcd(x,y)=gcd(p*x1,y)=gcd(x1,y),p是素数

int gcd3(int x,int y){
    if(x<y)
        return gcd3(y,x);
    if(y==0)
        return x;
    else{
        if(x&1==0){//x is even
            if(y&1==0)//y is even
                return gcd3(x>>1,y>>1)<<1;
            else//y is odd
                return gcd3(x>>1,y);
        }
        else{//x is odd
            if(y&1==0)//y is even
                return gcd3(x,y>>1);
            else//y is odd
                return gcd3(y,x-y);
        }

    }