HDU 1005 Number Sequence（数列）

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

【Description】

【题目描述】

A number sequence is defined as follows:

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).

一个数列定义如下：

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。

给定A,B和n，要求计算f(n)的值。

【Input】	【输入】
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.	多组输入。每个测试用例有一行3整数A，B和n(1 <= A, B <= 1000, 1 <= n <= 100,000,000)。最后一行为三个0，并且不被处理。

【Output】	【输出】
For each test case, print the value of f(n) on a single line.	对于每个测试样例，输出f(n)的值在单独一行。

【Sample Input - 输入样例】

【Sample Output - 输出样例】

1 1 3

1 2 10

0 0 0

【题解】

一般这种mod X的问题都与找循环节有关。

当 a = b = 7的时候，后面的数都是0，所以用前两个数1 1最为循环的开头很不明智。

因此我们直接从第三个数开始计算并找循环节。

【代码 C++】

 1 #include<cstdio>
 2 int main(){
 3     int i, a, b, n, data[50];
 4     while (scanf("%d%d%d", &a, &b, &n)){
 5         if (a + b + n == 0) break;
 6         a %= 7; b %= 7;  n -= 3;
 7         if (n < 0){ puts("1"); continue; }
 8         data[0] = (a + b) % 7; data[1] = (a*data[0] + b) % 7;
 9         for (i = 2; i <= n; ++i){
10             data[i] = (a*data[i - 1] + b*data[i - 2]) % 7;
11             if (data[i] == data[1] && data[i - 1] == data[0]){
12                 --i;
13                 break;
14             }
15         }
16         printf("%d
", data[n%i]);
17     }
18     return 0;
19 }