在清华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; }
Pingback引用通告: BZ编程小组 作品 | BZ编程小组