整数快速幂 & 快速幂取模
- 快速幂
- 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; }
最后
以上就是大力大白最近收集整理的关于整数快速幂 & 快速幂取模快速幂快速幂取模矩阵快速幂例题的全部内容,更多相关整数快速幂内容请搜索靠谱客的其他文章。
发表评论 取消回复