在斐波那契数列中，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; }
原文：https://www.cnblogs.com/wangzhe52xia/p/11627510.html
