Posted on 2011-04-25 22:34
lzh525 阅读(372)
评论(0) 编辑 收藏 引用 所属分类:
ＡＣＭ解题报告
#include
using namespace std;
int gcd(int x,int y)
{//欧几里得：辗转相除法
if(x>1,y>>1)
//若x偶，y奇, 则f(x,y)=f(x>>1,y)
//若x奇，y偶, 则f(x,y)=f(x,y>>1)
//若x,y都为奇数，f(x,y)=f(y,x-y),那么在f(x,y)=f(y,x-y)之后(x-y)是一个偶数，下一步会有除以2的操作，所以最坏情况下的时间复杂度O(log2(max(x,y)))
int f2(int x,int y)
{
if(x>1,y>>1)<<1);
else
return f2(x>>1,y);
}
else
{
if(y%2==0)
return f2(x,y>>2);
else
return f2(y,x-y);
}
}
}
int main()
{
int m,n;
while(cin>>m>>n)
{
printf("%d与%d的最大公约数为:\n",m,n);
//cout<