在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。
给定整数n，求Fibnmod10000Fibnmod10000。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含一个整数n。
当输入用例n=-1时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个整数表示结果。
每个结果占一行。
数据范围
0≤n≤2∗1090≤n≤2∗109
输入样例：
0
9
999999999
1000000000
-1
输出样例：
0
34
626
6875
代码;#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int mod = 10000;int mul(int f[2],int a[2][2]){ int c[2]; memset(c,0,sizeof(c)); for(int j=0;j<2;j++) { for(int k=0;k<2;k++) c[j] = (c[j]+(ll) f[k]*a[k][j])%mod; } memcpy(f,c,sizeof(c));}int mulself(int a[2][2]){ int c[2][2]; memset(c,0,sizeof(c)); for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { c[i][j] = (c[i][j] + (ll)a[i][k]*a[k][j])%mod; } } } memcpy(a,c,sizeof(c));}int main(){ int n; while(~scanf("%d",&n)&&n!=-1) { int f[2]={0,1}; int a[2][2] ={{0,1},{1,1}}; for(;n;n>>=1) { if(n&1)mul(f,a); mulself(a); } cout << f[0] << endl; } return 0;}