文章目录
- 前言
- 推导
- 暴力运算
- 快幂乘法
- 快速幂乘法
- 例题
- 快速取余
- 推导
- 例题
- 注意点
- 溢出问题
- 费马小定理
前言
说出来你可能不信，我先前竟然不知道快速幂乘法这玩意。虽然这玩意也很简单，但是有些小细节还是要注意一下的。
推导
下面过程直接用python代码演示更直观
暴力运算
在先前我们假设需要计算 pow(3,10),我们的相法可能是
1
2
3
4
5
6
7def mypow(a,n): for i in range(n-1): a*=a return a
时间复杂度为O（n）
所以我们可以拆分。
快幂乘法
那么这里我们可以考虑一下不用乘那么多次，我们可以考虑对半一下。
例如 310 = (32)5
此时我们的10就拆成了5.
快速幂乘法
但是我们的5还能再拆，于是我们可以一直拆下去，但是注意
35 的时候 5 是奇数，所以我们要拆成 3*34
1
2
3
4
5
6
7
8
9
10
11def mypow(a,n): res = 1 while(n>0): if(n%2==0): n = n/2 a = a*a else: n = n-1 res = res*a n = n/2
优化一下
1
2
3
4
5
6
7
8
9
10
11def mypow(a,n): res = 1 while(n>0): if(n%2!=0): n=n-1 res = res*a n = n/2 a = a*a return res
例题
Letcode 剑指Offer16 数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：输入：x = 2.10000, n = 3 输出：9.26100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution { public double myPow(double x, int n) { if(x == 0) return 0; long b = n; double res = 1.0; if(b < 0) { x = 1 / x; b = -b; } while(b > 0){ if((b & 1) == 1){//等价 b%2==1 res *= x; } x *= x; b >>= 1;//等价b/=2 } return res; } }
快速取余
推导
这个主要是和取余的性质挂钩。
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
所以我们在我们快速乘的过程当中我们就会使用到这种性质。
例如 33 % 2 = (3*32)%2 = 3%2 * (3 * 3)%2
所以我们如果想要取余的话，直接在原有的基础上取余即可
1
2
3
4
5
6
7
8
9
10
11def mypow(a,n,y): res = 1 while(n>0): if(n%2!=0): n=n-1 res = res*a % y n = n/2 a = a*a % y return res
把上面的例子往代码里面带入就是这个，也可以展开。
例题
这个是一个蓝桥杯的题目。
:
问题描述
//据说很多人的题目会有一大堆废话，本傻×就不在这里废话了。
就是叫你算A的B的C次方次方。
当然了，为了方便起见，把答案%1,000,000,007输出就好。
输入格式
一行，三个整数A，B，C，以空格隔开。
输出格式
输出A的B的C次方次方%1,000,000,007。
样例输入
3 4 5
样例输出
763327764
数据规模和约定
0≤A,B,C≤1,000,000,000
这里就是叫我们求
a^(b c) %1000000007
注意点
溢出问题
首先是我们java里面int 真难放不下。所以要用Long
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
38import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); String inputStr = s.nextLine(); String[] strArray = inputStr.split(" "); Long[] num = new Long[strArray.length]; for (int i = 0; i < num.length; i++) { num[i] = Long.parseLong(strArray[i]); } Long A = num[0]; Long B = num[1]; Long C = num[2]; Long mod = 1000000007L; System.out.printf(String.valueOf(PowerMod2(A,PowerMod2(B,C,mod),mod))); } public static Long PowerMod2(Long a,Long b,Long c){ Long ans = 1L; while (b>0){ if(b%2!=0){ //为奇数 ans = ans*a % c; } b = b/2; a = a*a %c; } return ans; } }
在这里你以为就完了嘛，我也以为是，然后。。。。。。
然后我又去查，没错我以为我又溢出了。后来我发现了这个东西
费马小定理
这个意思就是说
ab % k = ab%(k-1) % k
推理过程如下
ab % k
=a(k-1)*(k/(k-1)+k%(k-1) % k
=(a(k-1))(k/k-1) % k
=ab%(k-1) % k
所以代码调用要要写个mod-1
1
2System.out.printf(String.valueOf(PowerMod2(A,PowerMod2(B,C,mod-1),mod)));
然后就过来了
最后
以上就是舒适西牛最近收集整理的关于快速幂乘法&快速幂取余前言推导快速取余的全部内容，更多相关快速幂乘法&快速幂取余前言推导快速取余内容请搜索靠谱客的其他文章。
发表评论 取消回复