[UVa 11549]Calculator Conundrum
转载请注明出处：http://danihao123.is-programmer.com/
很有趣的一个题。
很明显，求出的结果一定会循环，形成一个环。然后呢？假如有一只乌龟和一只兔子在这个赛道上赛跑（同起点），兔子的速度是乌龟的两倍，那么最后兔子一定会“追上”乌龟，然后接下来的情况就是以前的循环了。
这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char buf[25];
int n;
inline ull next(ull x){
register ull res=0;
register int i,length;
memset(buf,0,sizeof(buf));
length=sprintf(buf,"%llu",x*x);
length=min(length,n);
for(i=0;i<length;i++){
res=res*10+buf[i]-'0';
}
return res;
}
int main(){
ull k1,k2,ans;
int T;
scanf("%d",&T);
while(T--){
scanf("%d%llu",&n,&k1);
ans=k1;
k2=k1;
do{
k1=next(k1);
k2=next(k2);
if(k2>ans)
ans=k2;
k2=next(k2);
if(k2>ans)
ans=k2;
}while(k1!=k2);
printf("%llu\n",ans);
}
return 0;
}
评论 (0)
