poj 3070 Fibonacci

 

Fibonacci Time Limit: 1000MSMemory Limit: 65536KTotal Submissions: 2134Accepted: 1471

Description

In the Fibonacci integer sequence, F₀ = 0, F₁ = 1, and F_n = F_{n − 1} + F_{n − 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 F_n.

Input

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.

Output

For each test case, print the last four digits of F_n. If the last four digits of F_n are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print F_n mod 10000).

Sample Input

0 9 999999999 1000000000 -1

Sample Output

0 34 626 6875

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:

.

Source

Stanford Local 2006

[Submit]   [Go Back]   [Status]   [Discuss]

 

/* 矩阵的方法。  {{F(n+1),F(n)}, {F(n),F(n-1)}}={{1,1}      ^n                         {1,0}} 令A(n)表示一个矩阵序列 A(n)={{F(n),F(n-1)},          {F(n-1),F(n-2)}那么A(2)={{1,1},{1,0}}，由那个表达式得到：A(n)=A(2)^(n-1)，A(2)是己知的2*2矩阵，现在的问题就是如何求 A(2)^n因为方阵的乘法有结合律，所以A(2)^n=A(2)^(n/2)*A(2)^(n/2)，不妨设n是偶数 所以求A(n)就可以化成求A(n/2)并作一次乘法，所以递归方程是：T(n)=T(n/2)+O(1) */ // 5144566 11410 3070 Accepted 204K 0MS C++ 1049B 2009-05-13 10:13:17 // 用矩阵做Fibonacci数  #include  < iostream > #define  MAX 2 using   namespace  std; typedef  struct  node {      int  matrix[MAX][MAX]; }Matrix; Matrix unit,init,result; int  n; void  Init()   // 初始化 {      int  i,j;      for (i = 0 ;i < 2 ;i ++ )          for (j = 0 ;j < 2 ;j ++ )         {             init.matrix[i][j] = 1 ;             unit.matrix[i][j] = (i == j);         }     init.matrix[ 1 ][ 1 ] = 0 ; } Matrix Mul(Matrix a,Matrix b)  // 矩阵乘法 {     Matrix c;      int  i,j,k;      for (i = 0 ;i < 2 ;i ++ )          for (j = 0 ;j < 2 ;j ++ )         {             c.matrix[i][j] = 0 ;              for (k = 0 ;k < 2 ;k ++ )                 c.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];              if (c.matrix[i][j] >= 10000 )   // 取余                 c.matrix[i][j] %= 10000 ;         }      return  c; } Matrix Cal( int  exp)   // 求幂 {     Matrix p,q;     p = unit;     q = init;      while (exp != 1 )     {          if (exp & 1 )         {             exp -- ;             p = Mul(p,q);         }          else         {             exp >>= 1 ;             q = Mul(q,q);         }     }     p = Mul(p,q);      return  p; } int  main() {      while (scanf( " %d " , & n) != EOF && n !=- 1 )     {          if (n == 0 )         {             printf( " 0\n " );              continue ;         }          if (n == 2 || n == 1 )         {             printf( " 1\n " );              continue ;         }         Init();         result = Cal(n - 1 );   // 求n-1次幂就好         printf( " %d\n " ,result.matrix[ 0 ][ 0 ]);     }      return   0 ; }

转载于:https://www.cnblogs.com/forever4444/archive/2009/05/13/1455684.html

相关资源：数据结构—成绩单生成器