快速幂和矩阵快速幂-模板

快速幂的思想就是减少相乘的次数，将原本n-1次的相乘减小到（lg（n））的复杂度；

a^b=(a^2)^(b/2)

这个式子由于/是整除，所以得分奇偶的不同情况，偶数时仍然成立，奇数时需要再乘上一个a；

所以快速幂就是将原本的以a为基本单位的连乘改成以a*a为单位的连乘；

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define ll long long 
 5 using namespace std;
 6 ll quickpow(ll a,ll n,ll mod)//计算的大多是要对mod；
 7 {
 8     int ans=1;
 9     while(n)
10     {
11         if(n&1)
12             ans=ans*a%mod;
13         a=a*a%mod;
14         b/=2;
15     }
16     return ans;
17 }
18 int main()
19 {
20     int a,b,mod;
21     cin>>a>>b>>mod;
22     int ans=quickpow(a,b,mod);
23     cout<<ans<<endl;
24     return 0;
25 }

矩阵的快速幂是在这个的思想的基础上的，对矩阵进行更新；

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define Max 10
 6 using namespace std;
 7 struct Matrix
 8 {
 9     int n,m;
10     int a[Max][Max];
11     Matrix operator * (Matrix b)
12     {
13         Matrix c;
14         c.n=n;
15         c.m=b.m;
16         memset(c.a,0,sizeof(c.a));
17         for(int i=0;i<n;i++)
18         {
19             for(int j=0;j<b.m;j++)
20             {
21                 for(int k=0;k<m;k++)
22                 {
23                     c.a[i][j]+=a[i][k]*b.a[k][j];
24                 }
25             }
26         }
27         return c;
28     }
29 };
30 Matrix quickpow(Matrix a,int n)
31 {
32         Matrix c;
33         c.n=a.n;
34         c.m=a.m;
35         for(int i=0;i<c.n;i++)
36         {
37             for(int j=0;j<c.m;j++)
38                 c.a[i][j]=(i==j);//初始化为单位矩阵；
39         }
40         while(n)
41             if(n&1)
42                 c=c*a;
43             a=a*a;
44         }
45         return c;
46 }
47 int main()
48 {
49     Matrix a,b;
50     scanf("%d%d",&a.n,&a.m);
51     for(int i=0;i<a.n;i++)
52     {
53         for(int j=0;j<a.m;j++)
54         {
55             scanf("%d",&a.a[i][j]);
56         }
57     }
58     b=quickpow(a,2);
59     for(int i=0;i<a.n;i++)
60     {
61         for(int j=0;j<a.m;j++)
62             printf("%d ",b.a[i][j]);
63         printf("
");
64     }
65     return 0;
66 }