-
用途：判断和求得一个循环数列的循环节
-
大致流程：
两人在如图的跑道赛跑
第一个人跑得慢，每次前进一步；第二个人快，每次前进两步
由于跑道性质，第二个先进入环状跑道后一直循环，直到遇到第一个人把他“追上”
由此就找到了循环节
通过证明可以发现第二个人只比第一个人多跑一圈
例题： UVA11549
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int n,k; 5 int b[200]; 6 int nxt(int n,int k) 7 { 8 if(!k) return 0; 9 ll k2=(ll)k*k; 10 int l=0; 11 while(k2>0) 12 { 13 b[l++]=k2%10; k2/=10; 14 } 15 if(n>l) n=l; 16 int ans=0; 17 for(int i=0;i<n;i++) 18 ans=ans*10+b[--l]; 19 return ans; 20 } 21 int main() 22 { 23 int t;scanf("%d",&t); 24 while(t--) 25 { 26 scanf("%d%d",&n,&k); 27 int ans=k; 28 int k1=k,k2=k; 29 do 30 { 31 k1=nxt(n,k1);//第一个孩子一次跑一步 32 k2=nxt(n,k2);//第二个孩子一次跑两步 第一步 33 if(k2>ans) 34 ans=k2; 35 k2=nxt(n,k2);//第二步 36 if(k2>ans) 37 ans=k2; 38 }while(k1!=k2); 39 printf("%d ",ans); 40 } 41 return 0; 42 }