Note: This article is available in Chinese only. 本文暂无英文版本。
View original
455. Sequence analysis#
比赛的时候逗了，往看空间限制了….
直接开了个set判重。。。显然MLE 了。。。
然后这道题的正解是 floyd判圈算法（也叫龟兔算法？）
http://www.cnblogs.com/oyking/p/4286916.html 这份题解讲得很详细
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 }