在斐波那契数列中,$Fib_0=0, Fib_1=1, Fib_n=Fib_{n-1}+Fib_{n-2} (n>1)$。
给定整数 $n$,求 $Fib_n \bmod 10000$。
输入格式
输入包含不超过 $100$ 组测试用例。
每个测试用例占一行,包含一个整数 $n$。
当输入用例 $n=-1$ 时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个整数表示结果。
每个结果占一行。
数据范围
$0 \le n \le 2 \times 10^9$
输入样例:
0
9
999999999
1000000000
-1
输出样例:
0
34
626
6875
#include <iostream>
using namespace std;
const int MOD = 10000;
// 定义矩阵乘法函数
void matrixMultiply(int F[2][2], int M[2][2])
{
int x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD;
int y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD;
int z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD;
int w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
// 定义快速幂函数
void power(int F[2][2], int n)
{
if (n == 0 || n == 1) return;
int M[2][2] = {{1, 1}, {1, 0}};
power(F, n / 2);
matrixMultiply(F, F);
if (n % 2 != 0) matrixMultiply(F, M);
}
// 计算斐波那契数列的余数
int fib(int n)
{
if (n == 0) return 0;
int F[2][2] = {{1, 1}, {1, 0}};
power(F, n - 1);
return F[0][0] % MOD;
}
int main()
{
int n;
while (cin >> n && n != -1) cout << fib(n) << '\n';
return 0;
}