UVa 11549 Calculator Conundrum / floyd判圈算法

题意是输入n k

然后只能显示k的前n位 然后k等于前n位的平方如此反复 求最大出现的数字

可以用map 或者set

新学了一个floyd判圈算法

就是比如2个赛跑 第二个比第一个速度快1倍 圆形跑道可以追上第一个人

这里就另k1做一次next k2做2次next 如果k1 == k2 就break

说明出现循环了

代码是书上的

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int buf[100]; int next(int n, int k) { if(!k) return 0; long long kk = (long long)k * k; int l = 0; while(kk) { buf[l++] = kk % 10; kk /= 10; } int ans = 0; for(int i = 0; i < n; i++) { ans *= 10; ans += buf[--l]; } return ans; } int main() { int T; int n, k; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &k); int ans = k; int k1 = k, k2 = k; do { k1 = next(n, k1); ans = max(ans, k1); k2 = next(n, k2); ans = max(ans, k2); k2 = next(n, k2); ans = max(ans, k2); }while(k1 != k2); printf("%d\n", ans); } return 0; }