1005 矩阵快速幂

本体有2种方法，一种是矩阵快速幂，一种是找规律。我用的是矩阵快速幂。

f(1)=1; f(2)=1; f(n)=( A*(f(n-1)) + B*(f(n-2)) )mod7;

[ f(n) ] = [ A B ] * [ f(n-1) ] => [ f(n) ] = [ A B ] (n-2） * [ f(1) ]

[ f(n-1) ] [ 1 0 ] [ f(n-2) ] => [ f(n-1) ] [ 1 0 ] [ f(2) ]

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <string.h>
 5 using namespace std;
 6 struct matrix{
 7     int a[2][2];
 8 }res,temp;
 9 matrix mul(matrix a,matrix b){
10     matrix t;
11     memset(t.a,0,sizeof(t.a));
12     int i,j,k;
13     for(i=0;i<2;++i)
14         for(j=0;j<2;++j)
15             for(k=0;k<2;++k){
16                 t.a[i][j]+=a.a[i][k]*b.a[k][j];
17                 t.a[i][j]%=7;
18             }
19     return t;
20 }
21 int main(){
22     int A,B,n,i,j;
23     while(~scanf("%d%d%d",&A,&B,&n)){
24         if(A==0&&B==0&&n==0) break;
25         if(n<=2) {printf("1
");continue;}
26 
27         memset(res.a,0,sizeof(res.a));
28         res.a[0][0]=res.a[1][1]=1;
29         temp.a[0][0]=A;
30         temp.a[0][1]=B;
31         temp.a[1][0]=1;
32         temp.a[1][1]=0;
33         n=n-2;
34         while(n){
35             if(n&1)
36                 res=mul(res,temp);
37             n>>=1;
38             temp=mul(temp,temp);
39         }
40         printf("%d
",(res.a[0][0]+res.a[0][1])%7 );
41     }
42 
43     return 0;
44 
45 }