Solution 计算器谜题
题目大意:每次平方并取前\(n\)位数字,问出现的所有数的最大值
分析:这题是从蓝书上看到的,学到了一个叫做\(Floyd\)判圈算法的神仙玩意儿.
简而言之,这个算法就是维护两个指针\(k1\),\(k2\),然后每次依题意让\(k1\)走\(1\)步,\(k2\)走\(2\)步,如果有环的话,那么\(k1\),\(k2\)一定会相遇(可以想象成追击问题,怎么又是小学奥数)
最后在\(k2\)取的所有值里面取最大值即可
#include <cstdio>
using namespace std;
typedef long long ll;
unsigned char tmp[32];
int t,n,k;
inline int nxt(int x){
ll res = 0,t = (ll)x * x;
int p = 0;
do{
tmp[++p] = t % 10;
t /= 10;
}while(t);
for(int i = p;i >= p - n + 1 && i >= 1;i--)res = res * 10 + tmp[i];
return res;
}
inline void solve(){
scanf("%d %d",&n,&k);
int ans = k,k1 = k,k2 = k;
do{
k1 = nxt(k1);
k2 = nxt(k2);if(k2 > ans)ans = k2;
k2 = nxt(k2);if(k2 > ans)ans = k2;
}while(k1 != k2);
printf("%d\n",ans);
}
int main(){
scanf("%d",&t);
while(t--)solve();
return 0;
}