HDU1005 Number Sequence【递推序列+模除】

问题链接：HDU1005 Number Sequence。

问题描述：参见上文。

问题分析：这是一个有关数列与模除的问题。

斐波拉契数列是人们熟悉的。这个问题的每一项都做了一个算术计算，然后用7进行模除。

根据数论的知识可知，模7的余数值是0-6。若对于正整数k和m，若f(k-2)=f(m-2)且f(k-1)=f(m-1)，则f(k)=f(k-2)+f(k-1)=f(m-2)+f(m-1)=f(m)，即如果k和m的前两项完全相同，则f(k)=f(m)。这样的数列，若干项之后，其值会循环出现，所以不必将其所有的项都算出来，只需要算出第一个循环的各个项即可。

因此，只需要构建一个长度为n的短数列，各项的值为定义公式计算出来的7的余数，需要知道的是n为多少。如果f(n+1)=1（f(1)=1）且f(n+2)=1（f(2)=1），那么就得到了所要求的n了。

程序说明：（略）。

AC的C语言程序如下：

/* HDU1005 Number Sequence */

#include <stdio.h>

int main(void)
{
    int a, b;
    long n;
    int t[102];
    int i;

    t[1] = 1;
    t[2] = 1;
    while(scanf("%d%d%ld", &a, &b, &n) != EOF) {
        if(a == 0 && b==0 && n==0)
            break;

        for(i=3; i<102; i++) {
            t[i] = (a * t[i-1] + b * t[i-2]) % 7;

            if(t[i] == 1 && t[i-1] == 1)
                break;
        }

        t[0] = t[i - 2];
        n %= i-2;

        printf("%d
", t[n]);
    }

    return 0;
}