杭电-1005 Number Sequence

很自然想到递归，写完注意到n的取值（ 1 <= n <= 100,000,000），递归肯定要报内存错了。

然后想到用栈，但是这么大的结构估计也开不出来。

一定是有什么不为人知的技巧在其中--

苦苦思索无果之后，开始百度。

什么循环节，什么数论，吓得我当场就关了电脑，摸了两天鱼（寒假）。

今日下决心要破这堵了，将之前搜索出来的网页仔细看了看，发现挺简单的。

f(n) 由f(n-1)和f(n-2)与常数AB决定，而f(n)的值一定小于7，只能为0-6这7个值。

f(n-1)和f(n-2)同样也只能为0-6这七个值，它们俩的组合决定了f(n)的值，这种组合有7X7=49种

当计算到f(50)的时候，一定有一种组合出现了重复。

组合重复，即f(n-1)，f(n-2)在之前已经出现过，由它们计算出的f(n)也必然出现过，以此类推。

不难发现，f(n)的结果出现了循环。

我们要做到的就是找到这个循环的长度，用n模上循环长度，结果的位置就出来了。

#include<iostream>
using namespace std;
int main()
{
    int A,B;
    int n;
    int a[50];
    while(cin>>A>>B>>n)
    {
        if(A==0&&B==0&&n==0)break;
        int i=3;
        a[1]=a[2]=1;
        for(i=3;i!=50;++i){
            a[i] = (A*a[i-1] + B*a[i-2])%7;
            if(a[i] == 1 && a[i-1] == 1)
                    break;
        }
        n = n%(i-2);
        if(n == 0)
            cout<<a[(i-2)]<<endl;
        else
            cout<<a[n]<<endl;
    }
    return 0;
}

由于一个小bug导致程序一直不通过，我调了很久非常丧气，于是一步一步将代码改成了链接里前辈已AC的代码，终于找到原因，所以你们能看到我的程序和链接里的基本一样。

参考链接：https://www.cnblogs.com/jasonJie/p/5999473.html