题目

Description

f(1) =1；
f(2)=1；
f(n)=(A*f(n-1)+B*f(n-2)) mod 7
给定A,B和n时，计算f(n)

Input

包含多组数据，每组测试数据占一行，包括3个整数，分别为A,B和n,其中：1<=A,B<=100, 1<=n<=100,000,000, 输入3个0表示输入结束。

Output

对于每组测试数据输出一个f(n)值，并且占一行。

Sample Input

1 1 3
1 2 10
0 0 0

Sample Output

2
5

题解

每组 A 、 B 都不同,而 n 最大 100000000
记忆化搜索没法用,直接计算绝对会超时,因此,找规律

先随便跑几个数据,看下规律
很容易发现最后数列会是循环的,但是循环的区间不一样长

理解下很容易明白
对于 f(n)=(A\*f(n-1)+B\*f(n-2)) mod 7
根据同余定理可以拆分成 f(n)=(A*f(n-1)) mod 7 + (B*f(n-2)) mod 7
两部分都只有7种情况,因此很容易就会出现规律,并且最长区间也只有 49

先运行一遍找到循环区间,然后直接取余映射到循环范围内即可

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
const int maxn = 50;
int f[maxn];
int A,B;
 
bool flag[maxn][maxn];
 
bool Do() {
    int n;
    scanf("%d%d%d",&A,&B,&n);
    if(A == 0 && B == 0 && n == 0)
        return false;
    A %= 7;
    B %= 7;
    memset(f,0,sizeof(f));
    memset(flag,false,sizeof(flag));
    f[1] = f[2] = 1;
    int T;
    for(int i = 3;;i++) {
        int a = (A*f[i - 1]) % 7;
        int b = (B*f[i - 2]) % 7;
        f[i] = (a + b) % 7;
        if(flag[a][b]) {
            T = i - 3;
            break;
        }
        flag[a][b] = true;
    }
 
 
    printf("%d\n",f[n = (n % T) ? (n % T) : T]);
 
    return true;
}
 
int main() {
    while(Do());
    return 0;
}