快速幂模板

下面是 m^n % k 的快速幂：

 1 // m^n % k
 2 int quickpow(int m,int n,int k)
 3 {
 4     int b = 1;
 5     while (n > 0)
 6     {
 7           if (n & 1)
 8              b = (b*m)%k;
 9           n = n >> 1 ;
10           m = (m*m)%k;
11     }
12     return b;
13 }

下面是矩阵快速幂：

 1 //HOJ 3493
 2 /*===================================*/
 3 || 快速幂（quickpow）模板 
 4 || P 为等比，I 为单位矩阵
 5 || MAX 要初始化！！！！
 6 ||
 7 /*===================================*/
 8 /*****************************************************/
 9 #include <cstdio>
10 const int MAX = 3;
11 
12 typedef  struct{
13         int  m[MAX][MAX];
14 }  Matrix;
15 
16 Matrix P = {5,-7,4,
17             1,0,0,
18             0,1,0,
19            };
20 
21 Matrix I = {1,0,0,
22             0,1,0,
23             0,0,1,
24            };
25            
26 Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
27 {
28        int i,j,k;
29        Matrix c;
30        for (i = 0 ; i < MAX; i++)
31            for (j = 0; j < MAX;j++)
32              {
33                  c.m[i][j] = 0;
34                  for (k = 0; k < MAX; k++)
35                      c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;
36                  c.m[i][j] %= 9997;
37              }
38        return c;
39 }
40           
41 Matrix quickpow(long long n)
42 {
43        Matrix m = P, b = I;
44        while (n >= 1)
45        {
46              if (n & 1)
47                 b = matrixmul(b,m);
48              n = n >> 1;
49              m = matrixmul(m,m);
50        }
51        return b;
52 }
53                /*************************************/
54 
55 int main()
56 {
57     Matrix re;
58     int f[3] = {2,6,19};
59     long long n;
60     while (scanf("%I64d",&n) && n != 0)
61     {
62           if (n == 1)
63              printf("1
");
64           else if (n <= 4)
65                   printf("%d
",f[n-2]);
66                else {
67                       re = quickpow(n - 4);
68                       printf("%d
",(((re.m[0][0]*f[2]) 
69                              + (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);
70                       }
71     }
72     return 0;
73 }