hdu 1005

这一题用到了快速幂的方法，还有就是构造矩阵……

#include "stdio.h"
#include "string.h"

void mult(int f[2][2],int y[2][2],int c[2][2])//求矩阵相乘
{
 int i;
 int a[2][2],b[2][2];
 memcpy(a,f,sizeof(int)*4);//这里也，要将数组复制过来，否则是会出错的，因为传过来的有可能是相同的矩阵相乘……
 memcpy(b,y,sizeof(int)*4);
 for(i=0;i<2;i++)
 {
  c[i][0]=(a[i][0]*b[0][0]+a[i][1]*b[1][0])%7;
  c[i][1]=(a[i][0]*b[0][1]+a[i][1]*b[1][1])%7;
 }
}

void pow(int f[2][2],int n)
{
 int s[2][2]={1,0,0,1};
 int a[2][2];
 int i;

 memcpy(a,f,sizeof(int)*4);//最好还是将原来的数组复制过来，这样我个人感觉也可以少犯一些错误
 
 for(i=0;n!=0;i++)//用快速幂的方法求a^n
 {
  if(n&(1<<i))
   mult(s,a,s);
  mult(a,a,a);
  n&=~(1<<i);
 }

 memcpy(f,s,sizeof(int)*4);
}

int main()
{
 int a,b,n;
 int ditui[2][2]={0,1,1,1};
 
 while(scanf("%d%d%d",&a,&b,&n)==3)
 {
  if(a==0&&b==0&&n==0)
   break;
  ditui[0][0]=0;
  ditui[1][0]=1;
  ditui[1][1]=a;
  ditui[0][1]=b;

  if(n<=2)
  {
   printf("1\n");
   continue;
  }

  pow(ditui,n-2);

  printf("%d\n",(ditui[0][1]+ditui[1][1])%7);//最后竟然忘记mod7了，汗~~~
 }

 return 0;
}