求最大公约数—-辗转相除法

在清华oj上遇到一道求最大公约数的题,做出来很简单,但跑分就不行了,数据大了总超时。我自己想的方法,最好的也不过是最后两组数据超时~~

http://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=32

 

后来查到了一种3000年前的求最大公约数的方法:辗转相除法~~

http://baike.baidu.com/view/255668.htm?fr=aladdin#3_2

于是,编成程序,所有数据完美跑出~~耗时短的难以置信~~~

 

#include

 

using namespace std;

 

long zhanzhuanxiangchu(long d,long e)

{

if(d%e==0) return e;

else return zhanzhuanxiangchu(e,d%e);

}

 

int main(void)

{

long a,b;

 

cin>>a;cin>>b;

 

cout<

 

 

//system(“pause”);

 

return 0;

}

求最大公约数—-辗转相除法》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.