• 用途：判断和求得一个循环数列的循环节

• 大致流程：

　　　　两人在如图的跑道赛跑

　　　　

　　　　第一个人跑得慢，每次前进一步；第二个人快，每次前进两步

　　　　由于跑道性质，第二个先进入环状跑道后一直循环，直到遇到第一个人把他“追上”

　　　　由此就找到了循环节

　　　　通过证明可以发现第二个人只比第一个人多跑一圈

• 所以这个算法的优点在于： 空间上不用储存每一步具体的值 将空间复杂度降到O(1)

• 具体证明看这里：     

 

例题： UVA11549

1 #include
      
        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
       
        ans)34                 ans=k2;35             k2=nxt(n,k2);//第二步 36             if(k2>ans)37                 ans=k2;38         }while(k1!=k2);39         printf("%d\n",ans);40     }41     return 0;42 }