fibonacci数列(二)

时间限制：

1000 ms | 内存限制：

65535 KB

难度：

3

 

描述

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.

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).

样例输入

091000000000-1

样例输出

0346875

1 //找周期  2 #include 
         
           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
         

 

1 //快速幂算法  2  #include
         
           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
            
              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             else21                 printf("%d\n",f[n]);22         }23         else24             printf("1\n");25     }26     return 0;27 }