快速求幂模板

#include <iostream>
using namespace std;
struct s
{
 int a[2][2];
};
int p;

s work(s x,s y)
{
 s c;
 for (int i=0;i<2;i++)
 {
  for (int j=0;j<2;j++)
  {
   c.a[i][j]=0;
   for (int k=0;k<2;k++)
    c.a[i][j]+=x.a[i][k]*y.a[k][j];
   c.a[i][j]%=p;
  } 
 }
 return c;
}

s mod(s t,int n)
{
 s m;
    if (n==0||n==1)
    {
  return t;
    }
  if (n%2)
 {
       m=mod(t,n/2);
    m=work(m,m);
    m=work(m,t);
 }
  else
  {
   m=mod(t,n/2);
          m=work(m,m);
  }
  return m;
}

int main()
{
 s t,m;
 t.a[0][0]=0;   t.a[0][1]=1;    t.a[1][0]=1;   t.a[1][1]=1;
 m=t;
 int n;
 while (cin>>n>>p)
 {
  int c=n;
  while(c>0)
  {
   if (c%2)
   {
    c--;
    m=work(m,m);
    m=work(m,t);
   }
   else
   {
    c=c>>1;
    m=work(m,m);
   }
  }
  cout<<m.a[1][1]<<endl;
 }
 return 0;
}