c语言实现:我们可以用利用矩阵乘法来计算Fibonacci的第n项 给出一个整数n,请求出F[n]的末四位(如果后4位中前面的位上的数字为0,则不需要输出这个0,例如,后4位是0056,则输出56 即可)。 输入格式 只有一行,即为整数N(0<=N<=1.000,000,000)。 输出格式 只有一行,为一个整数,即F[n]% 10000的余数。 输入样例 9输出样例 34
时间: 2023-02-09 13:41:14 浏览: 65
c语言实现如下:
#include <stdio.h>
#include <stdlib.h>
#define MOD 10000
typedef long long LL;
// 矩阵乘法
void matrix_multiply(LL A[2][2], LL B[2][2])
{
LL 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[k][j]) % MOD;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
A[i][j] = C[i][j];
}
// 矩阵快速幂
void matrix_pow(LL A[2][2], LL n)
{
if (n == 1)
return;
matrix_pow(A, n / 2);
matrix_multiply(A, A);
if (n % 2 == 1)
{
LL B[2][2] = {0, 1, 1, 1};
matrix_multiply(A, B);
}
}
int main()
{
LL n;
scanf("%lld", &n);
if (n == 0)
{
printf("0\n");
return 0;
}
LL A[2][2] = {0, 1, 1, 1};
matrix_pow(A, n - 1);
printf("%04lld\n", A[0][1]);
return 0;
}
代码中的矩阵快速幂思路就是,每次将矩阵乘自己,直到n变为1。
这样,我们就实现了Fibonacci数列求第n项的矩阵乘法算法。