航电oj 1005

image

这道题初看可以直接递归解决，但是 n 的取值过大时会发生栈溢出，无法解决这一问题。仔细思考之后发现，输入A、B、n之后，A、B的值就确定了，f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7的值只取决于 f(n - 1) 和 f(n - 2) 的值。

假如我们知道了A、B的值，那么 f(3) 的值就可以由递推式得出，f(4) 的值也可由 f(2) 和 f(3) 得出，就像多米诺骨牌一样，后面的所有都可以确定了。由此可知，我们知道前面 f(n - 1) 和 f(n - 2) 的值，就可以得出 f(n) 的值了。

f(n - 1) 和 f(n - 2) 的取值范围均为 0~6 共 7 种情况，两个的组合共 7×7=49 种情况， 也就是 50 次以后，一定会有重复的情况。比如 50 次里出现[0][0]两次，我们就可以断定 f(n) 的值是循环出现的，因为前面两个数一定可以确定第三个数，后面的数也都随之确定，所以再次出现相同的两个数时，下一个数也一定和上一次相等。（例如 f(3)=3，f(4)=4，而确定的 f(5)=5，当 f(35)=3，f(36)=4 的时候，f(37)一定等于5，循环的周期就是 35-3=32）。但是值得注意的是，循环的周期不一定是 49，可能不到 49 就开始循环了，因此我们还是需要找到循环周期是多少。

还有一点，f(1) 和 f(2) 是人为给出的，可能不在循环之内，因此我选择从 f(3) 开始算循环周期。

所以代码如下：

#include<stdio.h>

int main(){
    long a,b,n;
    while(scanf("%ld%ld%ld",&a,&b,&n) != EOF){
        if(a==0 && b==0 && n==0) return 0;

        int f[53];
        f[1]=1,f[2]=1;
        int t; //循环周期

        for(int i=3;i<53;i++){ //计算f[1]~f[52]的值
            f[i] = (a*f[i-1] + b*f[i-2]) % 7;
        }

        for(int j=5;j<53;j++){ //找循环周期t
            if(f[j]==f[3] && f[j+1]==f[4]){
                t = j-3; //从第三个开始找，要减3得到周期
                break;
            }
        }

        int ans = f[(n-3)%t+3]; //先减3算出在循环周期里的次序，再加3得到对应数组下标次序
        printf("%d\n",ans);
    }
    return 0;
}