题目是要求出斐波那契数列n项对一个正整数取模，那么可以把斐波那契数列取模后得到的数列周期求出来。
比如下面一个题目：求出f[n]的后4位，先求出数列对10000取模的周期，然后再查找即可。
1 #include<stdio.h> 2 #define N 15000 3 #define MOD 10000 4 int a[N]; 5 int main(void) 6 { 7 int i,n; 8 a[0]=0; 9 a[1]=1; 10 for(i=2;i<N;i++) 11 a[i]=(a[i-1]+a[i-2])%MOD; 12 while(scanf("%d",&n)&&n!=-1) 13 printf("%d\n",a[n%N]);return 0; 14 }
或者利用矩阵快速幂：
#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\n");
else{
while(n)
{
if(t&1)
{
AN(a,res);
n-=n&(-n);
}
t>>=1;
AN(a,a);
}
printf("%d\n",res[0][1]%MOD);
}
}
return 0;
}
矩阵A^13=A^*A^4*A;A^N可以这样求，每次求出A^k,k=N&(-N),然后N-=k，直到N为零。
版权声明：本文为rootial原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。