求最大公约数----gcd算法

gcd算法：全名 欧几里得算法 又称，用于计算两个a，b的。

其计算原理依赖于下面的定理：

定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。（greatest common divisor）缩写为gcd。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

下面是三种基本的不同求法：


1.基础的模运算

[cpp] view plaincopy

int gcd(int a,int b)
{
    int r;
    while(b>0)
    {
         r=a%b;
         a=b;
         b=r;
    }
    return a;
}

2.位运算计算

[cpp] view plaincopy

int gcd(int a,int b)
{
    while(b^=a^=b^=a%=b);
    return a;
}

3.递归方式实现

[cpp] view plaincopy

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