链接：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;
}
