Number Sequence（数学）

Number Sequence

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

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

 

 

Author

 

CHEN, Shunbao

 

       题意：

       给出 A （1 ~ 1000），B （1 ~ 1000），N （1 ~ 10 ^ 8），F [ 1 ] = F [ 2 ] = 1，后 F [ N ] =（A * F [ N - 1 ] + B * F [ N - 2 ] ）% 7。输出 F [ N ]。

 

       思路：

       数学。结果 % 7，说明 f 最多也只可能是 0 ~ 6 中的某一个数，模拟几组数据即可发现会有循环节。算出循环节后 F [ N % MOD ] 即是答案。循环节最多也只可能是 7 X 7 = 49 这么多，所以数组开 55 来保存循环节也就够了。

 

       AC：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int num[55];

int main () {
        int a, b, n;

        while (~scanf("%d%d%d", &a, &b, &n) && (a + b + n)) {
                int mod;
                num[1] = num[2] = 1;
                for (mod = 3; mod < 55; ++mod) {
                        num[mod] = (a * num[mod - 1] + b * num[mod - 2]) % 7;
                        if (num[mod] == 1 && num[mod - 1] == 1) {
                                mod -= 2;
                                break;
                        }
                }
                if (!(n % mod)) printf("%d\n",num[mod]);
                else printf("%d\n", num[n % mod]);
        }

        return 0;
}