在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)
给定整数 n,求 Fibnmod10000。
输入格式
输入包含不超过 100100 组测试用例。
每个测试用例占一行,包含一个整数
当输入用例 n=−1时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个整数表示结果。
每个结果占一行。
数据范围
0≤n≤2×10^9
输入样例:
0
9
999999999
1000000000
-1
输出样例:
0
解题思路:
矩阵求fib:
定义a[2][2] = {0,1,0,0} f[2][2]={0,1,1,1}
an=a0*f^n
最后a[0][0]就是答案
/*
矩阵求fib,
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 10000;
int mul(int a[][2],int b[][2])
{
int c[2][2] = {0};
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] + a[i][k] * b[j][k]) % MOD;
memcpy(a,c,sizeof c);
}
int fib(int n)
{
int a[2][2] = {0,1,0,0};
int f[2][2] = {0,1,1,1};
while (n)
{
if(n&1) mul(a,f);
mul(f,f);
n >>= 1;
}
return a[0][0];
}
int main()
{
int n;
while(cin>>n,n!=-1)
cout<<fib(n)<<endl;
return 0;
}