杭电ACM1005

杭电ACM1005

这道题一开始我采用的是递归的方法求解，也能够完美运行，但是提交到OJ之后，提示内存溢出，这说明递归的算法产生的内存开销超过了OJ的规则限制，必须采用其他的方法。
然后我们会发现在所有的运算后会有个mod操作，即C++的取余数操作，这个操作得出的值是有一定的周期性的，而且他的值必然在[0, 6]之间，也就是有7种情况，而每一次的操作需要两个f(n)的值进行操作，所以一共有7 * 7 = 49个周期，由此可以写出如下代码：

#include <iostream>

using namespace std;

int main()
{

    int A, B, n, i, f[53] = { 0 };
    while(cin >> A >> B >> n)
    {
        if(A ==  0 && B == 0 && n == 0)
            break;
        if(n == 1 || n == 2)
        {
            cout << '1' << endl;
            continue;
        }

        f[1] = 1, f[2] = 1;
        A %= 7, B %= 7;
        for(i = 3; i < 53; i++)
        {
            f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;
            if(f[i] == 1 && f[i - 1] == 1)
                break;
        }
        i -= 2;
        n %= i;
        f[0] = f[i];
        cout << f[n] << endl;
    }
    return 0;
}