hdu3117Fibonacci Numbers

对于这种用矩阵求完后4位，还得用公式求前4位的===

#include <iostream>
#include <stdio.h>
#include <math.h>
#define Mod 10000
using namespace std;
long long f[100];
const int MAX = 2;

typedef  struct{
        long long  m[MAX][MAX];
}  Matrix;

Matrix P = {0,1,
            1,1};

Matrix I = {1,0,
            0,1};

Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
       int i,j,k;
       Matrix c;
       for (i = 0 ; i < MAX; i++)
           for (j = 0; j < MAX;j++)
             {
                 c.m[i][j] = 0;
                 for (k = 0; k < MAX; k++)
                        c.m[i][j] += (a.m[i][k] * b.m[k][j])%Mod;
                 c.m[i][j] %= Mod;
             }
       return c;
}

Matrix quickpow(long long n)
{
       Matrix m = P, b = I;
       while (n >= 1)
       {
             if (n & 1)
                b = matrixmul(b,m);
             n = n >> 1;
             m = matrixmul(m,m);
       }
       return b;
}
int main()
{
       double log_s=0.0;
    Matrix tmp;
    int n,bit=0;
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=50;i++)
    {
     f[i]=f[i-1]+f[i-2];
     if (f[i]>=10000)
       { bit=i-1;break;      }
    }
    //cout<<f[12]<<endl;


    while(cin>>n)
    {
      if (n<=bit) cout<<f[n]<<endl;
      if (n>bit)
      {

        log_s=log10(1.0/sqrt(5)) +(double)n*log10((1.0+sqrt(5))/2.0);
        int ans_s=(int)(pow(10,log_s-(int)log_s+3));
        cout<<ans_s<<endl;
      }
    }
    return 0;
}