HDUnbsp;2855nbsp;Fibonaccinbsp;Check-up（数…

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2855

这题找规律比较难

代码：

#include<stdio.h>
int m;
__int64 a[2][2],b[2][2];

void Mul(__int64 c[2][2],__int64 d[2][2])
{
   __int64 x[2][2],y[2][2];

   x[0][0]=c[0][0];x[0][1]=c[0][1];
   x[1][0]=c[1][0];x[1][1]=c[1][1];

   y[0][0]=d[0][0];y[0][1]=d[0][1];
   y[1][0]=d[1][0];y[1][1]=d[1][1];

   c[0][0]=(x[0][0]*y[0][0]+x[0][1]*y[1][0])%m;
   c[0][1]=(x[0][0]*y[0][1]+x[0][1]*y[1][1])%m;
   c[1][0]=(x[1][0]*y[0][0]+x[1][1]*y[1][0])%m;
   c[1][1]=(x[1][0]*y[0][1]+x[1][1]*y[1][1])%m;
}

void POW(int n)
{
   if(n==1)
       return;
   POW(n/2);
   Mul(a,a);
   if(n%2==1)
       Mul(a,b);
   a[0][0]%=m;a[0][1]%=m;
   a[1][0]%=m;a[1][1]%=m;
}

int main()
{
   int ncase,n;
   scanf("%d",&ncase);
   while(ncase--)
   {
       scanf("%d%d",&n,&m);
       if(n==0)
           printf("0\n");
       else if(n==1)
           printf("%d\n",1%m);
       else
       {
           a[0][0]=b[0][0]=3;a[0][1]=b[0][1]=1;
           a[1][0]=b[1][0]=-1;a[1][1]=b[1][1]=0;
           POW(n-1);
           printf("%I64d\n",a[0][0]<0?a[0][0]+m:a[0][0]%m);
       }
   }
   return 0;
}