【Floyd判圈】计算器谜题

传送门:CodeVS4671


Floyd判圈算法:k1、k2同时操作,k1执行1遍,k2执行2遍;由于存在环,k2必定会等于k1


上代码比较简明易懂:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const LL a[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
LL n,m,k,ans;
LL nxt(LL n,LL x){x=x*x; while (x>=a[n]) x/=10; return x;}
int main(){
scanf("%lld",&m);
for (;m;m--){
scanf("%lld%lld",&n,&k);
LL k1=k,k2=k; ans=k;
do{
k1=nxt(n,k1);
k2=nxt(n,k2); if (k2>ans) ans=k2;
k2=nxt(n,k2); if (k2>ans) ans=k2;
}while(k1!=k2);
printf("%lld\n",ans);
}
return 0;
}