Uva(11549)(Calculator Conundrum)

链接：https://vjudge.net/problem/UVA-11549
思路：首先很容易猜到这个平方最后一定会循环，不然的话最大值就根本没法确定了，具体证明暂时没想到但很容易猜到，既然循环，自然而然想到应该用一个set来判断是否重复，于是很容易写出如下的循环版本
代码：

#include<cstdio>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,k;
set<int> j;

long long cal(long long w){
    while(w>=pow(10,n))w/=10;
    return w;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--){
        j.clear();
    scanf("%d%d",&n,&k);
    long long now = k;
    long long maxn = k;
    while(j.count(now)==0){
        j.insert(now);
        now*=now;
        if(now>=pow(10,n)){
            now = cal(now);
        }
        maxn = max(maxn,now);
    }
    printf("%lld\n",maxn);
    }
    return 0;
}

虽然能过，但是set似乎还是很占空间。这时看了刘汝佳大大大大神的做法，了解了一下floyd判圈，大概就是两个小孩跑步(具体表现为下述代码中k1或者k2，)，第二个以两倍于第一个的速度前进，当他们俩碰面的时候，正好多走了一个圈。

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,k;

long long calnext(long long w){
    w = w*w;
    while(w>=pow(10,n))w/=10;
    return w;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--){
    scanf("%d%d",&n,&k);
    long long now = k;
    long long maxn = k;
    long long k1 = k,k2=k;
    do{
        k1 = calnext(k1);//小孩1
        k2 = calnext(k2);if(k2>maxn)maxn = k2;//小孩2
        k2 = calnext(k2);if(k2>maxn)maxn = k2;
    }while(k1!=k2);//碰面，k2比k1刚好多走一圈
    printf("%lld\n",maxn);
    }
    return 0;
}