hdu1005 Number Sequence---找循环节

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1005
题目大意：

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
思路：

由于模7，循环节一定在49以内，所以计算前49位，找到循环节，直接输出a[n]即可。

start为循环节开始的下标，len为循环节长度，计算a[n]时，如果 n <= start，直接输出a[n],如果大于start，输出a[start + (n - start) % len]；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 #include<cmath>
 7 using namespace std;
 8 const int maxn = 1e4 + 10;
 9 typedef long long ll;
10 int T, n, m;
11 int a[maxn];
12 int main()
13 {
14     int x;
15     while(cin >> n >> m >> x && (n + m + x))
16     {
17         memset(a, 0, sizeof(a));
18         a[1] = 1, a[2] = 1;
19         bool flag = 0;
20         int start, len;
21         for(int i = 3; ; i++)
22         {
23             a[i] = n * a[i - 1] + m * a[i - 2];
24             a[i] %= 7;
25             for(int j = 1; j <= i - 2; j++)
26             {
27                 if(a[j] == a[i - 1] && a[j + 1] == a[i])
28                 {
29                     flag = 1;
30                     start = j;
31                     len = i - j - 1;
32                 }
33                 if(flag)break;
34             }
35             if(flag)break;
36         }/*
37         for(int i = 1; i < start; i++)cout<<a[i]<<" ";
38         for(int i = start; i <= start + len; i++)cout<<a[i]<<" ";
39         cout<<endl;
40         cout<<start<<" "<<len<<endl;*/
41         if(x <= start)cout<<a[x]<<endl;
42         else cout<<a[start + (x - start) % len]<<endl;
43     }
44     return 0;
45 }