プログラミングの美しさ:第二章数字の魅惑2.7最大公約数問題

/*
       :
     ，            (Greatest Common Divisor,GCD)。          ，        


  2:
       ，      。           x y，       x-y y；       x-y y           x y
f(x,y) = f(x-y,y)，      ，  x<y，     ，                    。

  3:
        :  y x  ，  y = k*y1,x = k*x1。   f(y,x) = k*f(y1,x1).
  x = p*x1,  p   ，  y%p != 0( y   p  ),  f(x,y) = f(p*x1,y) = f(x1,y)

2     ，               ，       2   2          ，    。
 p = 2
 x，y    ，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1)
 x   ，y   ,f(x,y) = f(2*x/2,y) = f(x/2,y) = f(x>>1,y)
 x   ，y   ,f(x,y) = f(x,y>>1)
 x,y    ，f(x,y) = f(y,x-y)(           ，    x y         )
         O(log2（max(x,y)）)

  :
1 100 100 210 001
120 200 021

8
12
  :

4
*/

/*
  :
1 f(x,y)  x y      ， k = x/y,b = x%y,  x = k*y + b。           x y，      b y;         b y     
      x y；x y     y x%y        、
f(x,y) = f(y,x%y)(x>=y>0)
2 return gcd_minus(a-b,b);//  gcd(a,b)  = gcd(a-b,b)  ，       ，    ，  :        ,
3 	if(y == 0)//         0，      x
	{
		return x;
	}
	else if((x & 1) == 0)//  x   ，x & 1 == 0
	{
		if((y & 1) == 0)//  y   
		{
			return (gcd_move(x >> 1,y >> 1) << 1);//               
*/

#include <stdio.h>

static int _iCnt1 = 0;
long long gcd(long long a,long long b)
{

	_iCnt1++;
	return !b ? a : gcd(b,a%b);
}

static int _iCnt2 = 0;
long long gcd_minus(long long a,long long b)
{

	_iCnt2++;
	if(a < b)//  gcd()            >=   ，     
	{
		return gcd_minus(b,a);
	}
	if(b == 0)//    
	{
		return a;
	}
	else
	{
		return gcd_minus(a-b,b);//  gcd(a,b)  = gcd(a-b,b)  ，       ，    ，  :        ,
	}
}

static int _iCnt3 = 0;
long long gcd_move(long long x,long long y)//   gcd
{
	
	_iCnt3++;
	if(x < y)
	{
		return gcd_move(y,x);
	}
	if(y == 0)//         0，      x
	{
		return x;
	}
	else if((x & 1) == 0)//  x   ，x & 1 == 0
	{
		if((y & 1) == 0)//  y   
		{
			return (gcd_move(x >> 1,y >> 1) << 1);//               
		}
		else
		{
			return gcd_move(x >> 1,y);
		}
	}
	else
	{
		if((y & 1) == 0)//  y   
		{
			return gcd_move(x,y >> 1);
		}
		else
		{
			return gcd_move(y,x-y);
		}		
	}
}

void swap(long long * pNum1,long long *pNum2)
{
	long long lTemp = *pNum1;
	*pNum1 = *pNum2;
	*pNum2 = lTemp;
}

void process()
{
	long long n,m;
	while(EOF != scanf("%lld %lld",&n,&m))
	{
		if(n < m)
		{
			swap(&n,&m);
		}
		printf("%lld
",gcd(n,m));
		printf("%lld
",gcd_move(n,m));
		printf("%d %d
",_iCnt1,_iCnt3);
		printf("%lld
",gcd_minus(n,m));
		printf("%d
",_iCnt2);
		
	}
}

int main(int argc,char* argv[])
{
	process();
	getchar();
	return 0;
}