杭电oj-1005-Number Sequence

其实写完下面的程序，就知道肯定过不了，内存消耗太大了，虽然已经用了尾递归，于是只好另寻出路。

#include <stdio.h>

int Func(int n, int a, int b, int f1, int f2);

int main()
{
    int a, b, n;
    
    while (1)
    {
        scanf("%d%d%d", &a, &b, &n);
        if (a == 0 && b == 0 && n == 0)
            break;
        printf("%d\n", Func(n, a, b, 1, 1));
    }
    return 0;
}


int Func(int n, int a, int b, int f1, int f2)
{
    if (n == 1)
        return f1;
    else
        return Func(n - 1, a, b, f2, (a * f2 + b * f1) % 7);
}

于是，发现因为取7的余数，怎么算都会回到1,1；于是出现了下面一段代码

#include <stdio.h>

int main()
{
    int a, b, n;
    int i, j;
    int cyc[100] = { 0 };//用于存储一组循环的结果
    int len;//循环结果的长度

    cyc[0] = 1; cyc[1] = 1;
    while (1)
    {

        scanf("%d%d%d", &a, &b, &n);
        if (a == 0 && b == 0 && n == 0)
            break;
        
        i = 2;
        //int cyc[100] = { 0 };
        do
        {
            cyc[i] = (a * cyc[i - 1] + b * cyc[i - 2]) % 7;
            i++;
        } while (cyc[i-1] != 1 || cyc[i - 2] != 1);
        len = i - 2;

        if (n%len == 0)
            printf("%d\n", cyc[len -1]);
        else
            printf("%d\n", cyc[n%len -1]);
    }
    return 0;
}

但是，还是超时了，明天再解决！
昨天想了想，超时应该是某项数据陷入了死循环数据
今天再想了想，循环节不超过 7^2 是肯定的，因为每两个数两两组合有7^2种可能，第50组数必定重复了前面出现过的数对（假设前面每个数对都不相同）。但是为啥循环节的长度为啥是49的因数这个没弄出来，以后再研究吧。
所有晚上回来写的代码就是用最大的循环节长度49作为数组长度。

#include <stdio.h>

int main()
{
    int a, b, n;
    int i, j;
    int cyc[100] = { 0 };//用于存储一组循环的结果
    int len;//循环结果的长度

    cyc[0] = 1; cyc[1] = 1;
    while (1)
    {

        scanf("%d%d%d", &a, &b, &n);
        if (a == 0 && b == 0 && n == 0)
            break;
        
        i = 2;
        //int cyc[100] = { 0 };
        for (i = 2; i < 49; i++)
        {
            cyc[i] = (a*cyc[i - 1] + b*cyc[i - 2])%7;
        }

        printf("%d\n", cyc[n % 49 - 1]);
    }
    return 0;
}