gcd函数

10进制取gcd

首先来个简单的gcd函数（递归的），应该一看就懂，这边就不讲了。

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

下面是优化，跟上面原理差不多，但是复杂度低一点。

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

二进制取gcd
从王玉大佬那学的

首先引入一个概念，“^”符号，是把一个十进制数，按位取异或。
举个栗子；
5 二进制为00101
9 二进制为01001
取异或以后为01100
为12
下面是用二进制将两数交换，属于快进快读，因为二进制算的比十进制快。

void swap( int &a , int &b ) 
{
    a=a^b;
    b=a^b;
    a=a^b;
}

然后用这个进行运算gcd函数

int gcd(int a,int b){
	while(b=^a=^b^=a%=b)//先取a和b的余数，再用二进制交换的法则进行
	//和前面十进制的运算法则是一样的
}