[UVa 11549]Calculator Conundrum
很有趣的一个题。
很明显，求出的结果一定会循环，形成一个环。然后呢？假如有一只乌龟和一只兔子在这个赛道上赛跑（同起点），兔子的速度是乌龟的两倍，那么最后兔子一定会“追上”乌龟，然后接下来的情况就是以前的循环了。
这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #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;} |
