快速求斐波那契数列第n项值poj3070 Fibonacci

#include<stdio.h> #define M 10000 struct node { int c[2][2]; }FAB; struct node mul(struct node *a,struct node *b) { struct node t; int i,j,k; for(i=0;i<2;i++) for(j=0;j<2;j++) t.c[i][j]=0; for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) { t.c[i][j]=(t.c[i][j]+a->c[i][k]*b->c[k][j])%M; } return t; } struct node power(struct node *a,int n) { struct node temp; temp.c[0][0]=1;temp.c[0][1]=0; temp.c[1][0]=0;temp.c[1][1]=1; while(n>0) { if(n&1) temp=mul(&temp,a); *a=mul(a,a); n>>=1; } return temp; } int main(void) { int n; while(~scanf("%d",&n)&&n>=0) { FAB.c[0][0]=1;FAB.c[0][1]=1; FAB.c[1][0]=1;FAB.c[1][1]=0; FAB=power(&FAB,n); printf("%d\n",FAB.c[1][0]); } }