fibonacci数列(二)
时间限制：
1000 ms | 内存限制：
65535 KB
难度：
3
- 描述
-
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
.Given an integer n, your goal is to compute the last 4 digits of Fn.
Hint
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
.Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
.- 输入
- The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.
- 输出
- For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).
- 样例输入
-
0 9 1000000000 -1
- 样例输出
-
0 34 6875
1 //找周期 2 #include <stdio.h> 3 4 #define N 20000 5 int a[N]={0,1}; 6 7 int init() 8 { 9 int i,j,k; 10 for(i=2;i<N;i++) 11 { 12 a[i]=(a[i-1]+a[i-2])%10000; 13 if(a[i]==0) 14 { 15 a[i+1]=(a[i]+a[i-1])%10000; 16 if(a[i+1]==1) 17 break; 18 } 19 } 20 return i; 21 } 22 23 int main() 24 { 25 int i,j,k; 26 int n; 27 int period = init(); 28 while(scanf("%d",&n),n!=-1) 29 { 30 n%=period; 31 printf("%d\n",a[n]); 32 } 33 return 0; 34 }
1 //快速幂算法 2 #include<stdio.h> 3 4 void fast_pow(int a1[][2], int a2[][2]) 5 { 6 int c[2][2]; 7 int i, j, k; 8 for (i=0; i<2; ++i) 9 { 10 for (j=0; j<2; ++j) 11 { 12 c[i][j] = 0; 13 for (k=0; k<2; ++k) 14 { 15 c[i][j] = (c[i][j] + a1[i][k] * a2[k][j]) % 10000; 16 } 17 } 18 } 19 for (i=0; i<2; ++i) 20 { 21 for (j=0; j<2; ++j) 22 { 23 a1[i][j] = c[i][j]; 24 } 25 } 26 } 27 28 int main() 29 { 30 int i,j,k; 31 int n; 32 while (scanf("%d", &n) , n != -1) 33 { 34 int a[2][2] = {{1, 1}, {1, 0}}; 35 int b[2][2] = {{1, 0}, {0, 1}};//单位矩阵 36 while (n) 37 { 38 if (n & 1) 39 fast_pow(b, a); 40 fast_pow(a, a); 41 n >>= 1; 42 } 43 printf ("%d\n", b[1][0]);//最后n必然从1变为0，所以最后一次总要执行 fast_pow(b, a); 44 } 45 return 0; 46 }
HDU 1005
f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
同样是构造矩阵
1 #include<stdio.h> 2 int main() 3 { 4 int f[200],a,b,n,i; 5 while(scanf("%d%d%d",&a,&b,&n),a||b||n) 6 { 7 if(n>2) 8 { 9 f[1]=f[2]=1; 10 for(i=3;i<200;i++) 11 { 12 f[i]=(a*f[i-1]+b*f[i-2])%7; 13 if(f[i-1]==1&&f[i]==1) 14 break; 15 } 16 i-=2;//LPP，最小正周期 17 n=n%i;//比如1~5是个循环周期，f(6)=f(1)、 18 if(n==0) 19 printf("%d\n",f[i]); 20 else 21 printf("%d\n",f[n]); 22 } 23 else 24 printf("1\n"); 25 } 26 return 0; 27 }
