GCD的不同写法(while、递归式辗转相除，异或交换两值，二进制筛因子)

while写法，在会递归发之前首次接触辗转相除的过程就用while模拟

LL gcd(LL a,LL b)
{
    while(b)
    {
        LL tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

然后是递归写法，最短的代码，简单明了，模拟的是辗转相除法过程

LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}

两个数字进行三次异或运算可以交换数值。
可以写为：

while（b>0）
{
     a=a%b;        /// -->求出余数赋给a；
     b=b^a;          ///-->通过亦或运算，b的值变为其他值
     a=a^b;          ///-->a的值变为原b的值
     b=b^a;          ///-->b的值变为原a的值 
}
return  a;

这样，当b为0的时候，a就是最大公约数，然后返回这个值即可

while(b^=a^=b^=a%=b);  

转自https://blog.csdn.net/u013533289/article/details/41217451

还有一种二进制gcd写法:

可以通过不断地筛去因子2来提高算法的效率，这样的2可以是公共的或单个的，总之不影响算法的正确性

那么为什么不是筛去因子3、因子4呢？

因为计算机只提供2进制的快速运算(按位)，所以判断a%2=?0可以直接写成!(a&1)，但是其它数是没有的，我们知道计算机做取模运算的效率是很低很低的。

证明过程：

GCD(x,y)=x (x==y)

GCD(x,y)=2*(GCD(x/2,y/2)) (!(x&1) and !(y&1))

GCD(x,y)=GCD(x/2,y) (!(x&1) and (y&1) 因为2显然不是公因数，所以我们可以果断地筛掉它)

GCD(x,y)=GCD(x,y/2) ((x&1) and !(y&1) 理由同上)

GCD(x,y)=GCD(x-y,y) (辗转相减)

证明和代码转自：https://www.cnblogs.com/wxjor/p/6086929.html

int GCD(int x,int y){
    int i=0,j=0;
    if(x==0) return y;//if和for一定不能反，要么会炸
    if(y==0) return x;//一个没用了就返回另一个
    for(i;0==(x&1);i++) x>>=1;//化简为n*(m^2)形式
    for(j;0==(y&1);j++) y>>=1;//化简为a*(b^2)形式
    if(i>j) i=j;//去最大 公 因数，当然是你有我有的了
    while(1){
        if(x<y) x^=y,y^=x,x^=y;//二进制交换，非常高级
        if(0==(x-=y)) return y<<i;//那么就把以前的次幂乘上去，辗转减操作
        while(0==(x&1)) x>>=1;//x减了y以后可能还是成为a*(b^2)形式，要继续筛去
    }
}