//本程序为最大公约数
//greatest common diviser GCD
//分成三种方法
//1、辗转相除法
// f(40,30)=f(30,10)=f(10,0)=10 求余
//2、由于求余复杂度较高，改为相减
// f(40,30)=f(30,20)=f(20,10)=f(10,10)=f(10,0)=10
//3、第三种方法
// 如果x,y为偶数，则直接除以2，否则采用方法二
#include <iostream>
#include <stdio.h>
using namespace std;
int gcd(int x,int y);
int gcd2(int x,int y);
int gcd3(int x,int y);
bool IsEven(int x);
int main()
{
int x,y;
cin >> x >>y;
cout <<gcd(x,y) <<endl;
cout <<gcd2(x,y)<<endl;
cout <<gcd3(x,y)<<endl;
//char c;
//scanf("%c",&c);
cin >> x;
return 0;
}
//1、辗转相除法
// f(40,30)=f(30,10)=f(10,0)=10 求余
int gcd(int x,int y)
{
if(y==0)
{
return x;
}
else
{
if(x>y)
{
return gcd(y,x%y);
}
else
{
return gcd(x,y%x);
}
}
//return (!y)? x:gcd(y,x%y);
}
//2、由于求余复杂度较高，改为相减
// f(40,30)=f(30,20)=f(20,10)=f(10,10)=f(10,0)=10
int gcd2(int x,int y)
{
if(x<y)
{
return gcd(y,x);
}
if(y==0)
{
return x;
}
else
{
return gcd(x-y,y);
}
}
//3、第三种方法
// 如果x,y为偶数，则直接除以2，否则采用方法二
int gcd3(int x,int y)
{
if(x<y)
{
return gcd(y,x);
}
if(y==0)
{
return x;
}
else
{
if(IsEven(x))
{
if(IsEven(y))
{
return (gcd(x>>1,y>>1)<<1);
}
else
{
return gcd(x>>1,y);
}
}
else
{
if(IsEven(y))
{
return gcd(x,y>>1);
}
else
{
return gcd(x,y);
}
}
}
}
//判断是否是偶数
bool IsEven(int x)
{
if(x&0x01)
{
return false;
}
else
{
return true;
}
}
