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

2019-04-13 12:39发布

站内文章 / 模拟电子
16162 0 1409
题目是要求出斐波那契数列n项对一个正整数取模，那么可以把斐波那契数列取模后得到的数列周期求出来。 比如下面一个题目：求出f[n]的后4位，先求出数列对10000取模的周期，然后再查找即可。 1 #include 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) 11 a[i]=(a[i-1]+a[i-2])%MOD; 12 while(scanf("%d",&n)&&n!=-1) 13 printf("%d ",a[n%N]);return 0; 14 } 或者利用矩阵快速幂： #include #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为零。

热门文章