# 杰拉斯的博客

## [ACM_HDU_1005]Number Sequence

### Number Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53991 Accepted Submission(s): 12146

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

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

#### Output

For each test case, print the value of f(n) on a single line.

```
1 1 3
1 2 10
0 0 0
```

#### Sample Output

```2
5
```

```#include<stdio.h>
int main(){
int A, B, n, i;
while(scanf("%d%d%d", &A, &B, &n) != EOF){
if(A == 0 && B == 0 && n == 0)
break;
int f[3] = {1, 1, 0};
for(i = 2; i < n; ++i){
f[i % 3] = (A * f[(i + 2) % 3] + B * f[(i + 1) % 3]) % 7;
printf("%d\n", f[i % 3]);
}
printf("%d\n", f[(i + 2) % 3]);
}
return 0;
}
```

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

```#include<stdio.h>
int main(){
int A, B, n, z = 1;
int f[50] = {1, 1, 1};
while(scanf("%d%d%d", &A, &B, &n) != EOF){
if(A == 0 && B == 0 && n == 0)
break;
for(int i = 3; i < 50; ++i){
f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;
if(f[i - 1] == 1 && f[i] == 1){
z = i - 2;
break;
}
}
printf("%d\n", f[n % z]);
}
return 0;
}
```

f[n]：1 1 0 0 0 0 0 ...

```#include<stdio.h>

int main(){
int A, B, n, z = 1;
int f[54] = {0, 1, 1};
//取54是因为第0位不使用，第1,2位固定为1，加49最大周期及最后判断周期所用2位，最大共需用54位。
while(scanf("%d%d%d", &A, &B, &n) != EOF){
if(A == 0 && B == 0 && n == 0)
break;
for(int i = 3; i < 54; ++i){
f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;
//printf("%d ", f[i]);
if(i > 5){
if(f[i - 1] == f[3] && f[i] == f[4]){
z = i - 4;
break;
}
}
}
//printf("\n%d\n", z);
if(n > 2)
printf("%d\n", f[(n - 3) % z + 3]);
else
printf("1\n");
}
return 0;
}
```

1. 所以为何会wa呢？？？