求最大公约数

利用计算最大公约数的三条性质，用递归方法计算两个整数的最大公约数。 

n性质1：如果x>y，则x和y的最大公约数与x-y和y的最大公约数相同，即 gcd(x,y)=gcd(x-y,y)    x>y

n性质2：如果y>x，则x和y的最大公约数与x和y-x的最大公约数相同，即 gcd(x,y)=gcd(x,y-x)     x<y

n性质3：如果x=y，则x和y的最大公约数与x值和y值相同，即 gcd(x,y)=x=y

1、辗转相除法

int getDivGCD(int nA, int nB)
{
    int nMax = nA>nB?nA:nB;
    int nMin = nA<nB?nA:nB;
    int nMod = nMax%nMin;
    if (!nMod) {
        return nB;
    }
    return getGCD(nMin, nMod);
}

2、更相减损发

int getGCD(int nA,int nB)
{
    int nMax = nA>nB?nA:nB;
    int nMin = nA<nB?nA:nB;
    if (!(nMax%nMin)||nMin==1) {
        return nMin;
    }
    int nDiff = nMax-nMin;
    return getGCD(nMin, nDiff);

}

3、求多个数的最大公约数

int getGCD(stack<int> vInt)
{
    while (vInt.size()>=2) {
        int nA = vInt.top();
        vInt.pop();
        int nB = vInt.top();
        vInt.pop();
//        int nGCD = getGCD(nA, nB);
        int nGCD = getDivGCD(nA, nB);
        vInt.push(nGCD);
    }
    return vInt.top();
}