整数快速幂 & 快速幂取模
- 快速幂
- a^b^的朴素算法
- 快速幂的原理
- 快速幂【代码】
- 快速幂取模
- 幂取模的朴素的实现
- 快速幂取模原理
- 快速幂取模【代码】
- 矩阵快速幂
- 矩阵快速幂【代码】
- 例题
- P1226 【模板】快速幂||取余运算
- P3390 【模板】矩阵快速幂
快速幂
所谓的快速幂，其目的是为了快速求幂，将时间复杂度从O（n）朴素算法的降到O（logn）。
假如现在要求ab，按照朴素算法，就是将a连乘b次，时间复杂度为O(b)，即O（n）级别。
ab的朴素算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// O(n) #include<cstdio> // a^b的朴素算法 int pow(int a,int b) { int ans=1; while(b) { ans*=a; b--; } return ans; } int main() { int a,b; scanf("%d%d",&a,&b); printf("%dn",pow(a,b)); }
快速幂的原理
还是原来的ab，我们会发现，其实指数b是可以拆成二进制的。通过式子a(m+n) =(am )* (a n)，我们可以发现，一旦指数b拆成二进制，那么ab也可以进行相应的拆分。
例如，当b=11时，b的二进制为1011，即11 = 1*(20) +1*(21) + 1*(23)。则a11 = a^ (1*(20) +1*(21) + 1*(23)) =(a1) * (a2) *(a3)， 可以看到通过二进制转换，我们只需要进行3次计算，而用朴素算法我们需要进行11次计算。
接着就是如何判断一个数在二进制形式的某个位置是0还是1，以及具体的代码实现了。
因为是二进制，我们很容易联想到位运算，这里我们需要用到与运算&和右移运算>>。
- · &运算：通常用于二进制取位操作，例如一个数x & 1的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性，如果x&10，则x为偶数；如果x&11，则x为奇数。
- · >>运算：在这里是作为除法来使用，例如一个数x，x >> 1就表示x右移一位，即x=x/2。注意： 移位符号右侧的整数表示的是2的幂
- · << : 左移运算符，num << 1,相当于num乘以2,表示加0。
- · >>> : 无符号右移,也叫逻辑位移，忽略符号位，空位都以0补齐
快速幂【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25//【快速幂】 #include<cstdio> #include<iostream> using namespace std; // 快速幂的核心代码 int pow(int a,int b) { int ans=1,base=a;// ans：幂的结果；base：底数a while(b) { if(b & 1) { ans=ans*base; } base=base*base; b = b >> 1; } return ans; } int main() { int a,b; scanf("%d%d",&a,&b); printf("结果：%dn",pow(a,b)); }
快速幂取模
所谓的快速幂取模，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。下面我们以(ab) mod c为例。
幂取模的朴素的实现
1
2
3
4
5
6
7
8
9
10int pow_mod(int a,int b,int c) { int ans = 1; for(int i = 1;i <= b;i++) { ans = ans * a; } ans = ans % c; return ans; }
缺点：这个方法存在着明显的问题，如果a和b过大，很容易就会溢出。
快速幂取模原理
我们知道，模运算与基本四则运算类似，具体如下图：
这里用第四条公式：(ab)mod c = (a mod c)b mod c，由公式可以看出先让a关于c取余，这样可以大大减少a的大小。
快速幂取模【代码】
方法一
1
2
3
4
5
6
7
8
9
10
11int pow_mod(int a,int b,int c) { int ans = 1; a = a % c; //加上这一句 for(int i = 1;i <= b;i++) { ans = ans * a; } ans = ans % c; return ans; }
既然某个因子取余之后相乘再取余保持余数不变，那么新算得的ans也可以进行取余，所以得到比较良好的改进版本。积的取余等于取余的积的取余。
方法二
1
2
3
4
5
6
7
8
9
10
11int pow_mod(int a,int b,int c) { int ans = 1; a = a % c; //加上这一句 for(int i = 1;i <= b;i++) { ans = (ans * a)%c;// 这里再取一次余 } ans = ans % c; return ans; }
以上方法的时间复杂度均为O（n），在c过大的条件下，很容易超时。因此，我们需要用到快速幂取模来降低时间复杂度。
方法三
快速幂取模算法依赖于以下明显的公式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// time：O(logN) // 这里不考虑指数为负数的情况 int pow_mod(int a,int b,int c) { int ans = 1,base=a;// ans：结果；base：底数 base = base % c; //【考虑0次方的情况】 if(b==0) { return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 } while(b) { if(b & 1) // 与运算，判断奇偶性 ans = (ans*base) % c; b = b >> 1;// 右移一位，相当于除2 base = (base * base) % c; } return ans; }
矩阵快速幂
矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素算法的O（n）的时间复杂度，降到O（logn）。
一般求一个矩阵的n次方，我们会通过连乘n-1次来得到它的n次幂。（朴素算法）但做下简单的改进就能减少连乘的次数，方法如下：
把n个矩阵进行两两分组，比如：A * A * A * A* A * A=(AA)(AA)(AA)，这样变的好处是，你只需要计算一次AA然后将结果A*A连乘自己两次就能得到A^6，算一下发现这次一共乘了3次，少于原来的5次。
我们还可以取A^3作为一个基本单位。原理都一样：利用矩阵乘法的结合律，来减少重复计算的次数。
以上都是取一个具体的数来作为最小单位的长度，这样做虽然能够改进效率，但缺陷也是很明显的，取个极限的例子（可能有点不恰当，但基本能说明问题），当n无穷大的时候，你现在所取的长度其实和1没什么区别。
所以就需要我们找到一种与n增长速度”相适应“的”单位长度“，那这个长度到底怎么去取呢？？？这点是我们要思考的问题。既然要减少重复计算，那么就要充分利用现有的计算结果！怎么充分利用计算结果呢？？？这里考虑二分的思想。。
我们首先要认识到这一点：任何一个整数N，都能用二进制来表示。（又是二进制，可见其重要性）；我们可以将指数用二进制表示。比如A18 = （A16）*（A2），因为18 (10)=10010（2）,显然采取这样的方式计算时因子数将是log（n）级别的（原来的因子数是n）。不仅这样，因子间也是存在某种联系的，比如A4可以通过两个A2相乘得到，A8可以通过两个A4相乘得到，类似更高介，这点也充分利用了现有的结果作为有利条件。
矩阵快速幂【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40// 将二维数组放入一个结构体中 struct Mat { int mat[105][105];// 具体二维数组大小视具体情况而定 }; // 重载*运算符 // 矩阵A、B均为n阶方阵 Mat operator*(Mat A,Mat B) { Mat temp; //memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】 for(int i =0 ; i < n ; i++) { for(int j = 0 ; j < n ;j++) { temp.mat[i][j]=0;// 在这里将矩阵temp置零【零矩阵】 for(int k = 0 ;k < n ;k++) { temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod; } } } return temp;// 返回矩阵A*B的结果 } // 重载^运算符 Mat operator^(Mat A, k) Mat base; // 将矩阵base置为单位矩阵【单位矩阵】 for(int i=0;i<n;i++) base.mat[i][i]=1; // 快速幂【核心代码】 while(k) { if(k & 1) base = base * A; A = A * A; k = k >> 1; } return base; }
例题
P1226 【模板】快速幂||取余运算
输入输出样例
输入样例#1：
2 10 9
输出样例#1：
2^10 mod 9=7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35//【快速幂取模】 //用时: 21ms / 内存: 792KB #include<iostream> #include<cstdio> using namespace std; // a的b次方对c取模 // 注意类型要用long long // 取模运算【(a*b)%c == ((a%c)*(b%c))%c】 long long pow_mod(long long a,long long b,long long c) { long long ans = 1,base=a; base = base % c; //【考虑0次方的情况】【坑点，最后一组数据WA】 // 数据：1^0 % 1；结果：0。 if(b==0) { return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 } while(b) { if(b & 1)ans = (ans*base) % c; b = b >> 1; base = (base * base) % c; } return ans; } long long a,b,mod;// 注意类型 int main() { scanf("%lld%lld%lld",&a,&b,&mod); long long result=pow_mod(a,b,mod); printf("%lld^%lld mod %lld=%lldn",a,b,mod,result);// 注意输出格式 }
P3390 【模板】矩阵快速幂
输入输出样例
输入样例#1：
2 1
1 1
1 1
输出样例#1：
1 1
1 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88// 利用快速幂的思想,根据矩阵的结合律,可以递归二分求解 //【矩阵快速幂】 #include<iostream> #include<cstdio> #include<cstring> //包含memset函数 using namespace std; long long mod=1e9+7; long long n,k;// 注意类型要为long long，不然全部WA // 结构体存一个二维数组(矩阵)，可以直接return出来【一点好处】 struct Mat { long long mat[105][105]; }; //输入优化【适用于正负整数】 inline long long read() { long long X=0,w=0; char ch=0; while(!isdigit(ch)) { w|=ch=='-'; ch=getchar(); } while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } // 重载*运算符 Mat operator*(Mat A,Mat B) { Mat temp; //memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】 for(int i =0 ; i < n ; i++) { for(int j = 0 ; j < n ;j++) { temp.mat[i][j]=0;// 可以在这里做零矩阵，省一点时间 for(int k = 0 ;k < n ;k++) { temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod; } } } return temp;// 返回矩阵A*B的结果 } // 重载^运算符 Mat operator^(Mat A,long long k)//【坑点】这里的k一开始没有long long，导致全部WA { Mat base; // 将矩阵base置为单位矩阵【单位矩阵】 // 只需矩阵主对角线的元素为1即可，故可以只要一个循环 for(int i=0;i<n;i++) base.mat[i][i]=1; // 矩阵快速幂【核心代码】 while(k) { if(k&1) base = base * A; A = A * A; k = k >> 1; } return base; } int main() { n=read();// 输入优化 k=read();// 输入优化 Mat ans; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ans.mat[i][j]=read();// 输入优化 } } ans=ans^k;// ans^k【矩阵快速幂】 // 输出矩阵 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%lld ",ans.mat[i][j]); } puts("");// 这里是换行，相当于printf("n"); } return 0; }
最后
以上就是大力大白最近收集整理的关于整数快速幂 & 快速幂取模快速幂快速幂取模矩阵快速幂例题的全部内容，更多相关整数快速幂内容请搜索靠谱客的其他文章。
发表评论 取消回复