本文共 977 字,大约阅读时间需要 3 分钟。
直接模拟计算过程。 可以看出计算器显示出来的数是循环的,关键在于模拟的过程中,怎样判断是否循环了。
可以采用STL中的map或set,不过效率较低。hash的话耗很大的空间。
从大白上可以知道还有一种叫做“Floyd判圈法”的东西。就是假设有两个小孩子在一个圆圈跑道上赛跑,同时出发,但其中一个小孩的速度是另一个的两倍,所以跑得快的小孩将“追上”跑得慢的小孩(已经超过n圈了)。当超过的那一刻,可以肯定的是,此时快的小孩已经至少跑了1圈以上了,也就是“经过了一个循环”。那么只要模拟跟踪记录快的就可以了。
#include#include #include #include 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;}
转载地址:http://pszni.baihongyu.com/