sgu 455. Sequence analysis （floyd 判圈算法，O(1)空间复杂度求循环节）

 1    /*************************************************************************
 2    	> File Name: code/2015summer/#5/CC.cpp
 3    	> Author: 111qqz
 4    	> Email: rkz2013@126.com 
 5    	> Created Time: 2015年07月30日 星期四 21时02分17秒
 6     ************************************************************************/
 7    #include<iostream>
 8    #include<iomanip>
 9    #include<cstdio>
10    #include<algorithm>
11    #include<cmath>
12    #include<cstring>
13    #include<string>
14    #include<map>
15    #include<set>
16    #include<queue>
17    #include<vector>
18    #include<stack>
19    #define y0 abc111qqz
20    #define y1 hust111qqz
21    #define yn hez111qqz
22    #define j1 cute111qqz
23    #define tm crazy111qqz
24    #define lr dying111qqz
25    using namespace std;
26    #define REP(i, n) for (int i=0;i<int(n);++i)  
27    typedef long long LL;
28    typedef unsigned long long ULL;
29    const int inf = 0x7fffffff;
30    const int LIM = 2E6;
31    LL a,b,c;
32    LL next (LL x)
33    {
34        return (a*x+x%b)%c;
35    }
36    int main()
37    {
38        cin>>a>>b>>c;
39        LL x = next(1);
40        LL y = next(next(1));
41        int v = 1;
42        while (v<=LIM &&x!=y)
43        {
44    	x = next(x);  //乌龟走一步
45    	y = next(next(y)); //兔子走两步
46    	v++;
47        }
48        if (v>LIM)   //在规定范围内找不到循环节（兔子没有和乌龟到同一个位置）
49        {
50    	puts("-1");  
51    	return 0;
52        }
53    
54        x = 1;
55        int mu = 0;  //找到循环节的起点
56        while (x!=y) 
57        {
58    	x = next(x);
59    	y = next(y);
60    	mu++;
61        }
62        
63        int lam = 1; //循环节的长度
64        y = next(x);
65        while (mu+lam <= LIM  &&x!=y)
66        {
67    	y = next(y);
68    	lam++;
69        }
70        if (mu+lam<=LIM)
71        {
72    	printf("%d\n",mu+lam);
73        }
74        else
75        {
76    	puts("-1");
77        }
78    
79    	return 0;
80    }
81    
82