不理解矩阵快速幂如何用于求斐波那契数列第n项%m的余数,

不理解矩阵快速幂如何用于求斐波那契数列第n项%m的余数,
In the Fibonacci integer sequence,F0 = 0,F1 = 1,and Fn = Fn − 1 + Fn − 2 for n ≥ 2.For example,the first ten terms of the Fibonacci sequence are:
0,1,1,2,3,5,8,13,21,34,…
Given two integers n and m,your goal is to compute the value of Fn mod m.
Input
The input test file will contain multiple test cases.Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000) and m(where 0

按照正常的逻辑是只要求a[2][2]={1,1,1,0}这个矩阵的n次方就可以得到斐波那契数列的第n项（即a[0][1]）的值.但是你忽略了一点,就是你在求a[0][1],a[1][0],a[1][1]的值的时候你的a[0][0]的值其实已经改变了,导致你求得的a[0][1]的值不正确,继而影响到a[1][0]和a[1][1]的值.
因此,我们在遍历这四个值的时候是不能改变其中任何一个的,只有改完之后才能去改变它的值.所以我们可以用几个变量先将求得的新矩阵各值存起来,如下：
#include<stdio.h>
int a[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用两个二维数组表示快速幂算法要用到的矩阵
int main()
{
 int n,m,i,j,t,u;
 int a1,a2,a3,a4;
 while(scanf("%d %d",&n,&m)!=EOF)
 {
  if(m==-1 && n==-1)//当输入的m.n值为-1时结束整个算法
   return 0;
  /*以下是对于第n项斐波那契数的计算*/
  if(n==0)
   a[0][0]=0;
  else if(n==1 || n==2)
   a[0][0]=1;
  else
  {
   for(i=3;i<=n;i++)
   {
    a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];
    a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];
    a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];
    a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];
    a[0][0]=a1;
    a[0][1]=a2;
    a[1][0]=a3;
    a[1][1]=a4;
   }
  }
  t=a[0][0];
  a[0][0]=1;//重置矩阵
  a[0][1]=1;
  a[1][0]=1;
  a[1][1]=0;
  if(m==0)
   a[0][0]=0;
  else if(m==1 || m==2)
   a[0][0]=1;
  else
  {
   for(j=3;j<=m;j++)
   {
    a1=a[0][0]*b[0][0]+a[0][1]*b[1][0];
    a2=a[0][0]*b[0][1]+a[0][1]*b[1][1];
    a3=a[1][0]*b[0][0]+a[1][1]*b[1][0];
    a4=a[1][0]*b[0][1]+a[1][1]*b[1][1];
    a[0][0]=a1;
    a[0][1]=a2;
    a[1][0]=a3;
    a[1][1]=a4;
   }
  }
  u=a[0][0];
  a[0][0]=1;//重置矩阵
  a[0][1]=1;
  a[1][0]=1;
  a[1][1]=0;
  t=t%u;
  printf("%d\n",t);
 }
 return 0;
}
 
还有一点,就是你的矩阵相乘后两项写错了,自己对比一下改过来吧.
 
这样就能得到你想要的结果了.
再问： 主要是n要取到十亿，而时限是三秒，你这样求的话应该数据范围不够，同时也会超时吧？
再答： 请先采纳，后回答
再问： 已采纳快回答吧
再问： 已采纳快回答吧
再问： 六天了，没空讲解下？？？