[UVa 11549]Calculator Conundrum
很有趣的一个题。
很明显,求出的结果一定会循环,形成一个环。然后呢?假如有一只乌龟和一只兔子在这个赛道上赛跑(同起点),兔子的速度是乌龟的两倍,那么最后兔子一定会“追上”乌龟,然后接下来的情况就是以前的循环了。
这种神奇的算法叫做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; }