Fibonacci数列--矩阵乘法优化

#include<cstdio>
int n,p,t,b[3];
long long  a[3][3],c[3][3],d[3][3];
int ch(int x)
{
    c[1][1]=c[2][2]=1;
    c[1][2]=c[2][1]=0;//保证c[][]第一次与a[][]相乘时，值不变；
    while(x>1)
    {   
        int h=(x/2)*2;
        if(x!=h){
            for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++) {d[i][j]+=(a[i][k]*c[k][j])%p;}/*将多出的a[][]存到c[][]中,不懂的回炉快速幂;*/
            for(int i=1;i<=2;i++)
                  for(int j=1;j<=2;j++) {c[i][j]=d[i][j];d[i][j]=0;}
        }
        for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        for(int k=1;k<=2;k++) d[i][j]+=((a[i][k]%p)*(a[k][j]%p))%p;
        for(int i=1;i<=2;i++)
              for(int j=1;j<=2;j++) {a[i][j]=d[i][j];d[i][j]=0;}
        x=x/2;
    }
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    for(int k=1;k<=2;k++) d[i][j]+=(a[i][k]*c[k][j])%p;//将多出的c[][]与a[][]相乘；
    return (d[1][1]+d[2][1])%p;//fn=f1*d[1][1]+f0*d[2][1],矩阵乘法化简后得到的;
}
int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        for(int i=1;i<=2;i++)
          for(int j=1;j<=2;j++) d[i][j]=0;
        a[1][1]=a[1][2]=a[2][1]=1;
        a[2][2]=0;
        b[0]=1;b[1]=1;b[2]=2;//各种初始化；
        scanf("%d%d",&n,&p);
        if(n<3) printf("%d",b[n]%p);
        else{
            int ans=ch(n-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}