杭电_ACM_Number Sequence

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

Sample Input

1 1 3
1 2 10
0 0 0

Sample Output

2
5

View Code

 1 #include <stdio.h>
 2 int main()
 3 {
 4     int n, A, B, a[100], T, i;
 5     while (scanf("%d %d %d", &A, &B, &n) != EOF)
 6     {
 7         if (n == 0 && A == 0 && B == 0)
 8             break;
 9         a[1] = 1;
10         a[2] = 1;
11         if (n == 1 || n == 2)
12         {
13             printf("%d\n", a[n]);
14             continue;
15         }
16         if (A % 7 == 0 && B % 7 == 0)
17         {
18             printf("0\n");
19             continue;
20         }
21         for (i = 3; i < 100; i++)
22         {
23             a[i] = (A * a[i - 1] + B * a[i - 2]) % 7;
24             if (a[i] == 1 && a[i - 1] == 1)
25             {
26                 T = i - 2;
27                 break;
28             }
29         }
30         if (n % T == 0)
31             n = T;
32         else
33             n %= T;
34         printf("%d\n", a[n]);
35     }
36     return 0;
37 }

My process:

firstly,

View Code

 1 #include <stdio.h>
 2 int f(int A, int B, int n)
 3 {
 4     if (n == 1)
 5         return 1;
 6     else if (n == 2)
 7         return 1;
 8     else 
 9         return (A * f(A, B, n - 1) + B * f(A, B, n - 2)) % 7;
10 }
11 int main()
12 {
13     int n, A, B, result;
14     while (scanf("%d %d %d", &A, &B, &n) != EOF)
15     {
16         A %= 7;
17         B %= 7;
18         if (n == 0 && A == 0 && B == 0)
19             break;
20         result = f(A, B, n);
21         printf("%d\n", result);
22     }
23     return 0;
24 }

it's Runtime Error(STACK_OVERFLOW).

secondly,

View Code

 1 #include <stdio.h>
 2 int main()
 3 {
 4     int n, A, B, result, a, b;
 5     while (scanf("%d %d %d", &A, &B, &n) != EOF)
 6     {
 7         if (n == 0 && A == 0 && B == 0)
 8             break;
 9         a = 1;
10         b = 1;
11         A %= 7;
12         B %= 7;
13         if (n == 1 || n == 2)
14         {
15             printf("%d\n", a);
16             continue;
17         }
18         for (int i = 3; i <= n; i++)
19         {
20             result = (A * b + B * a) % 7;
21             a = b;
22             b = result;
23         }
24         printf("%d\n", result);
25     }
26     return 0;
27 }

it's Time Limit Exceeded.

thirdly,

View Code

 1 #include <stdio.h>
 2 #define MAX 100000003
 3 int a[MAX];
 4 int main()
 5 {
 6     /**/
 7     int n, A, B, result;
 8     a[1] = 1;
 9     a[2] = 1;
10     while (scanf("%d %d %d", &A, &B, &n) != EOF)
11     {
12         A %= 7;
13         B %= 7;
14         if (n == 0 && A == 0 && B == 0)
15             break;
16         if (n == 1 || n == 2)
17         {
18             printf("%d\n", a[n]);
19             continue;
20         }
21         for (int i = 3; i <= n; i++)
22         {
23             a[i] = (A * a[i - 1] + B * a[i - 2]) % 7;
24         }
25         printf("%d\n", a[n]);
26     }
27     return 0;
28 }

it's Memory Limit Exceeded.

---------------------------

Key points

firstly, it's easy to get that it is circulatory. Because the result is zero to six, and if you want to get the continuing one. it will be emerged in 50 times, but if A, B are the multiple of 7, the resulte is zero when n >= 3.

secondly, pay attention to details, if n is the mutiple of 7, you must set n to T.

last but not least, for either question, you must have clear thought and pay attention to details.