数论--快速幂,矩阵快速幂

1.快速幂：

当求a的b次方的时候，我们可以写一个函数一次循环求出，又可以用math文件里面的pow(double a,double b)解决

但是，当b非常大还要取模呢？O（n）的时间复杂度也不行怎么办？

可以用快速幂的方法：

要求a^b时，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时

　　　　　　　　　　　　 a^11=a^(2^0+2^1+2^3)=a^(2^0)*a^(2^1)*a^(2^3)

实现时要用到位运算：

b&1是取b二进制的末尾

b>>1是去掉b二进制的末尾

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4  
 5 #define ll long long 
 6  
 7 ll pow_mod(ll a,ll b,ll p)  //(a^b)%p 
 8 {
 9      ll ans=1;
10      while(b)
11      {
12          if(b&1)
13          {
14              ans=(ans*a)%p;
15          }
16          a=(a*a)%p;
17          b>>=1;
18      }
19      return ans;
20  }
21  
22  
23  int main()
24  {
25      ll a,b,p;
26      cin>>a>>b>>p;
27      cout<<pow_mod(a,b,p)<<endl;  
28  }

其中，a=(a*a)%p理解起来就是：第0次a=a^(2^0)；//初始值 ,第一次a=a*a相当于a^(2^1),第二次相当于a^(2^2).......a^(2^n)，再结合上面a^11=a^1011(二进制）=a^(2^0)*a^(2^1)*a^(2^3),

对应的就是，在第0次，第1次，第3次的时候,ans=(ans*a)%p;

而在第0次，第1次，第3次的时候ans要更新,是因为11的二进制1011的第0位，第1位，第3位是1（即if(b&1)，当前b的末尾是1）

讲解over，例题POJ 1995

2.矩阵快速幂：

原理与快速幂一样，不过就是把整数换成了矩阵，把整数的乘法换成了矩阵的乘法

先贴出代码：

 1 # include<cstdio>
 2 # include<cstring>
 3 using namespace std;
 4 
 5 #define NUM 50
 6 int MAXN,n,mod;
 7 
 8 struct Matrix//矩阵的类
 9 {
10     int a[NUM][NUM];
11     void init()           //将其初始化为单位矩阵
12     {
13         memset(a,0,sizeof(a));
14         for(int i=0;i<MAXN;i++)
15             a[i][i]=1;
16     }
17 } A;
18 
19 Matrix mul(Matrix a,Matrix b)  //(a*b)%mod  矩阵乘法
20 {
21     Matrix ans;
22     for(int i=0;i<MAXN;i++)
23         for(int j=0;j<MAXN;j++)
24         {
25             ans.a[i][j]=0;
26             for(int k=0;k<MAXN;k++)
27                 ans.a[i][j]+=a.a[i][k]*b.a[k][j];
28             ans.a[i][j]%=mod;
29         }
30     return ans;
31 }
32 
33 Matrix pow(Matrix a,int n)    //(a^n)%mod  //矩阵快速幂
34 {
35     Matrix ans;
36     ans.init();
37     while(n)
38     {
39         if(n%2)//n&1
40             ans=mul(ans,a);
41         n/=2;
42         a=mul(a,a);
43     }
44     return ans;
45 }
46 
47 void output(Matrix a)//输出矩阵
48 {
49     for(int i=0;i<MAXN;i++)
50         for(int j=0;j<MAXN;j++)
51             printf("%d%c",a.a[i][j],j==MAXN-1?'
':' ');
52 }
53 int main()
54 {
55     Matrix ans;
56     scanf("%d%d%d",&MAXN,&n,&mod);
57     for(int i=0;i<MAXN;i++)
58         for(int j=0;j<MAXN;j++)
59         {
60             scanf("%d",&A.a[i][j]);
61             A.a[i][j]%=mod;
62         }
63     ans=pow(A,n);
64     output(ans);
65     return 0;
66 }

请看到，mul() 函数，这个是矩阵的乘法

再看到第33行pow()函数，这个就是矩阵快速幂，跟上面的快速幂比较，是不是很像？

只不过用mul() 函数代替了 a=(a*a)%p的运算罢了

讲解over