Fibonacci数列对任何数取模都是一个周期数列

题目是要求出斐波那契数列n项对一个正整数取模，那么可以把斐波那契数列取模后得到的数列周期求出来。

比如下面一个题目：求出f[n]的后4位，先求出数列对10000取模的周期，然后再查找即可。

#include<stdio.h>
#define N 15000
#define MOD 10000
int a[N];
int main(void)
{
    int i,n;
    a[0]=0;
    a[1]=1;
    for(i=2;i<N;i++)
        a[i]=(a[i-1]+a[i-2])%MOD;
    while(scanf("%d",&n)&&n!=-1)
        printf("%d
",a[n%N]);return 0;
}

或者利用矩阵快速幂：

#include<stdio.h>
#define MOD 10000
void AN(int a[][2],int b[][2])
{
    int a1,a2,a3,a4;
    a1=(a[0][0]%MOD*b[0][0]%MOD+a[0][1]%MOD*b[1][0]%MOD)%MOD;
    a2=(a[0][0]%MOD*b[0][1]%MOD+a[0][1]%MOD*b[1][1]%MOD)%MOD;
    a3=(a[1][0]%MOD*b[0][0]%MOD+a[1][1]%MOD*b[1][0]%MOD)%MOD;
    a4=(a[1][0]%MOD*b[0][1]%MOD+a[1][1]%MOD*b[1][1]%MOD)%MOD;
    b[0][0]=a1;
    b[0][1]=a2;
    b[1][0]=a3;
    b[1][1]=a4;
}
int main(void)
{
    int res[2][2],a[2][2];
    int n;
    while(scanf("%d",&n)&&n!=-1)
    {
        int t=n;
        res[0][0]=res[1][1]=a[0][0]=a[0][1]=a[1][0]=1;
        a[1][1]=res[0][1]=res[1][0]=0;
        if(n==0)
            printf("0
");
            else{
                while(n)
                {
                    if(t&1)
                    {
                        AN(a,res);
                        n-=n&(-n);
                    }
                    t>>=1;
                    AN(a,a);
                }
                printf("%d
",res[0][1]%MOD);

            }
    }
    return 0;
}

　矩阵A^13=A^*A^4*A;A^N可以这样求，每次求出A^k,k=N&(-N),然后N-=k，直到N为零。