参考:http://www.docin.com/p-40388609.html

代码:

#include<stdio.h>

//用结构体定义矩阵
typedef struct{
long long m_00; //数值很大long long类型.
long long m_01;
long long m_10;
long long m_11;
}Matrix2By2;

/*------------两个矩阵相乘-----------------*/
Matrix2By2 MatrixMultiply(Matrix2By2 matrix1,Matrix2By2 matrix2)
{
Matrix2By2 matrix;
matrix.m_00=matrix1.m_00*matrix2.m_00+matrix1.m_01*matrix2.m_10;
matrix.m_01=matrix1.m_00*matrix2.m_01+matrix1.m_01*matrix2.m_11;
matrix.m_10=matrix1.m_10*matrix2.m_00+matrix1.m_11*matrix2.m_10;
matrix.m_11=matrix1.m_10*matrix2.m_01+matrix1.m_11*matrix2.m_11;
return matrix;
}
/*------------求矩阵 的N次方--------------*/
Matrix2By2 MatrixPower(unsigned int n)
{
Matrix2By2 matrix;
Matrix2By2 matrix_unit; //初始矩阵(1,1,1,0)
matrix_unit.m_00=(long long)1;
matrix_unit.m_01=(long long)1;
matrix_unit.m_10=(long long)1;
matrix_unit.m_11=(long long)0;
if(n==1)    //如果是1次方,就是矩阵本身
{
   matrix.m_00=(long long)1;//要数值转换
   matrix.m_01=(long long)1;
   matrix.m_10=(long long)1;
   matrix.m_11=(long long)0;
}
else if(n%2==0) //如果N是偶数,则先开方,再平方
{
   matrix=MatrixPower(n/2);
   matrix=MatrixMultiply(matrix,matrix);
}
else if(n%2==1) //如果N是奇数
{
   matrix=MatrixPower((n-1)/2);
   matrix=MatrixMultiply(matrix,matrix);
   matrix=MatrixMultiply(matrix,matrix_unit); //{zh1}还要乘以一个初始矩
}
return matrix; //返回矩阵
}
/*--------------------------------------*/
void main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
   if(n==0)    //f(0)=0
    printf("0\n\n");
   else if(n==1)   //f(1)=1
    printf("1\n\n");
   else
   {
    Matrix2By2 PowerNMinus2=MatrixPower(n-1);
    printf("%lld\n\n",PowerNMinus2.m_00);
   }
}
}

对于LONG LONG型范围内可行,如果是超大数.那还是没有足够的内存存储的.