算法题：uva 11549 - Calculator Conundrum （Floyd判圈法）

算法题：uva 11549 - Calculator Conundrum （Floyd判圈法）2014-03-17 csdn shuangde800题目链接

直接模拟计算过程。可以看出计算器显示出来的数是循环的，关键在于模拟的过程中，怎样判断是否循环了。

可以采用STL中的map或set，不过效率较低。hash的话耗很大的空间。

从大白上可以知道还有一种叫做“Floyd判圈法”的东西。就是假设有两个小孩子在一个圆圈跑道上赛跑，同时出发，但其中一个小孩的速度是另一个的两倍，所以跑得快的小孩将“追上”跑得慢的小孩（已经超过n圈了）。当超过的那一刻，可以肯定的是，此时快的小孩已经至少跑了1圈以上了，也就是“经过了一个循环”。那么只要模拟跟踪记录快的就可以了。

#include<iostream>#include<cstdio>#include<cstring>#include<set>using namespace std;typedef long long int64;char buf[12];int64 getNext（int n, int64 k）{int64 now = （int64）k*k;int len = 0;int64 tmp = now;while（tmp>0）{ ++len; tmp /= 10; }while（len-n > 0） { --len; now /= 10; }return now;}int main（）{int nCase, n;int64 k;scanf（"%d", &nCase）;while（nCase--）{cin >> n >> k;int64 ans = k;int64 slow=k, fast=k;do{slow = getNext（n, slow）;fast = getNext（n, fast）;ans = max（ans, fast）;fast = getNext（n, fast）;ans= max（ans, fast）;} while（slow ！= fast）;cout << ans << endl;}return 0;}