最大公约数 ACM
两个数的最大公约数
–来源于百度空间
最大公约数最经典的算法欧几里得，下面对欧几里得算法进行基本证明，假设用f（x，y）表示x y的最大公约数，取k=x/y,b=x%y，则x=ky+b,如果一个整数能够同时整除x和y，则必能同时整除b和y，能够同时整除b和y的数也必能同时整除x和y，即x和y的最大公约数和b和y的最大公约数是相同的，即有f（x，y）=f（y，x%y）（x>=y>0），如此处理便可把原问题转化为求两个更小的数的最大公约数，知道其中一个数为0，剩下的另外一个数就是两者的最大公约数，则直接用递归实现：
int gcd(int x,int y)
{
}
解法2
在解法1中用到了取模运算，取模在计算机中是非常昂贵的开销，那我们能不能不取模呢？
采用与欧几里得相应的分析，如果一个数能够同时整除x和y，则必能够同时整除x-y，和y，而能够同时整除x-y和y的数，也必能够同时整除x和y，即x和y的最大公约数与x-y和y的最大公约数相同，即f（x，y）=f（x-y，y）
int gcd(int x,int y)
{
}
解法3
解法2同样具有缺陷，如果遇到（100000000，1），就很尴尬了！
我们知道2是一个素数，同时对于二进制的大整数而言，可以很容易的除以2和乘以2的运算转换成移位运算，从而避免解法一的大整数除法，和解法二的多次迭代
原理：1、f(x,y)=k*f(x1,y1)；2、如果x=p*x1，假设p是素数，并且y%p!=0，那么f(x,y)=f(p*x1,y)=f(x1,y)。
由此可得到算法为：不断的对x和y做除2操作，直至两者均不能被2整除，采用辗转相减法，获得一个可被2整除的数，继续做除2操作，循环，直至两数之一为0。详细描述如下：
若x，y均为偶数，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1)
若x为偶数，y为奇数，f(x,y) = f(x/2,y) = f(x>>1,y)
若x为奇数，y为偶数，f(x,y) = f(x,y/2) = f(x,y>>1)
若x，y均为奇数，f(x,y) =f(y,x-y)
代码
int gcd(int a,int b)
{
if(a==b) return a;
if((a&1)==0)
{
if((b&1)==0)
return gcd(a>>1,b>>1)<<1;
else
return gcd(a>>1,b);
}
else
{
if((b&1)==0)
return gcd(a,b>>1);
else
return gcd(((a>b)?(a-b):(b-a))>>1,(a+b)>>1);
}
}