公司网站重新建站通知,证券投资网站建设,网站设计术语,wordpress 手工网站在斐波那契数列中#xff0c;Fib00,Fib11,FibnFibn−1Fibn−2(n1)
给定整数 n#xff0c;求 Fibnmod10000。
输入格式
输入包含不超过 100100 组测试用例。
每个测试用例占一行#xff0c;包含一个整数
当输入用例 n−1时#xff0c;表示输入终止#xff0c;且该…在斐波那契数列中Fib00,Fib11,FibnFibn−1Fibn−2(n1)
给定整数 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}
ana0*f^n 最后a[0][0]就是答案
/*矩阵求fib
*/
#include iostream
#include cstring
#include algorithmusing namespace std;
const int MOD 10000;int mul(int a[][2],int b[][2])
{int c[2][2] {0};for(int i0;i2;i)for(int j0;j2;j)for(int k0;k2;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(n1) mul(a,f);mul(f,f);n 1;}return a[0][0];
}int main()
{int n;while(cinn,n!-1)coutfib(n)endl;return 0;
}
