HOJ 3117 Fibonacci Numbers（矩阵快速幂，对数求数字的高位）

矩阵快速幂，对数求数字的高位
本题要点：
1、斐波那契数列 第40 项超过 8位数， 因此前面的39项打表
2、fib数列，可以通过矩阵的幂运算来计算，因此，后4位转化为 矩阵的快速幂
3、前4位，通过fib数列的通项公式和对数来计算，参考：
点这里

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 40;	// 第40 项超过 8位数
const int MaxN = 2, mod = 1e4;
int fab[N];
int n;struct Matrix
{
    int m[MaxN][MaxN];Matrix(){
    memset(m, 0, sizeof m);}
};Matrix multi(Matrix a, Matrix b)
{
    Matrix res;for(int i = 0; i < MaxN; ++i)for(int j = 0; j < MaxN; ++j)for(int k = 0; k < MaxN; ++k){
    res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;}return res;
}Matrix fastm(Matrix a, int n)
{
    Matrix res;for(int i = 0; i < MaxN; ++i)res.m[i][i]	= 1;while(n){
    if(n & 1){
    res = multi(res, a);}a = multi(a, a);n >>= 1;}return res;
}void solve()
{
    //先求前4位double f = n * log10((1 + sqrt(5)) / 2) - 0.5 * log10(5);long long integer = f;double decimal = f - integer;while(pow(10, decimal) < 1000){
    decimal = decimal + 1;}int ans = pow(10, decimal);printf("%d...", ans);//再求后4位Matrix a;a.m[0][0] = a.m[0][1] = a.m[1][0] = 1;a.m[1][1] = 0;Matrix res = fastm(a, n);printf("%04d\n", res.m[0][1]);
}int main()
{
    fab[0] = 0, fab[1] = 1;for(int i = 2; i < N; ++i){
    fab[i] = fab[i - 1] + fab[i -2];}while(scanf("%d", &n) != EOF){
    if(n < N){
    	printf("%d\n", fab[n]);continue;}solve();}return 0;
}/* 0 1 2 3 4 5 35 36 37 38 39 40 64 65 *//* 0 1 1 2 3 5 9227465 14930352 24157817 39088169 63245986 1023...4155 1061...7723 1716...7565 */