Fibonacci Numbers hoj 求斐波那契前四位和后四位

#include <stdio.h>#include <cmath>#include <cstring>#include <iostream>#define c (sqrt(5.0)+1.0)/2.0#define mod 10000using namespace std;typedef long long LL;LL tmp[3][3],a[3][3],ans[3][3];void mul(LL a[][3],LL b[][3]){    for(int i=1; i<=2; i++)        for(int j=1; j<=2; j++)        {            tmp[i][j]=0;            for(int k=1; k<=2; k++)            {                tmp[i][j]+=a[i][k]*b[k][j];                if(tmp[i][j]>=mod) tmp[i][j]%=mod;            }        }    memcpy(a,tmp,sizeof(tmp));}void pow(LL a[][3],LL b[][3],int n){    a[1][1]=a[2][2]=1;    a[1][2]=a[2][1]=0;    while(n)    {        if(n&1) mul(a,b);        mul(b,b);        n>>=1;    }}int main(){    int f[40];    f[0]=0;    f[1]=1;    for(int i=2; i<=39; i++)        f[i]=f[i-1]+f[i-2];    int x;    while(scanf("%d",&x)!=EOF)    {        if(x<=39)        {            printf("%d\n",f[x]);            continue;        }        double ans1=-0.5*(log10(5.0))+double(x)*log10(c);        ans1-=int(ans1);        ans1=pow(10.0,ans1);        while(ans1<1000) ans1*=10;        int ans2;        memset(ans,0,sizeof(ans));        a[1][1]=a[1][2]=a[2][1]=1;        a[2][2]=0;        pow(ans,a,x-1);        ans2=ans[1][1]%mod;        printf("%d...%04d\n",int(ans1),ans2);    }    return 0;}