快速幂求余算法

71 阅读 0 评论 47 点赞

我是靠谱客的博主知性人生，这篇文章主要介绍快速幂求余算法，现在分享给大家，希望可以做个参考。

快速幂求余算法

为了防止在快速幂乘中导致溢出，我们往往需要对计算结果取余，下面介绍快速幂算法过程以及如何防止溢出。

公式： $a^b$ $m o d$ $c$

原始代码：

复制代码

1
2
3
4
5
6
res = 1;
for(int i=1; i <= b; i++){
	res = res*a;
}
res = res % c;

改进一：

前提： $a^b$ $m o d$ $c$ = $a mod c）^b$ $m o d$ $c$

为了防止 $a$ 过大，我们可以按照上述的公式对代码进行如下的改进：

复制代码

1
2
3
4
5
6
7
res = 1;
a = a % c  //对a取余
for(int i=1; i <= b; i++){
	res = res*a;
}
res = res % c;

改进二：

由于某个因子取余之后相乘再取余保持余数不变，那么新算得的res也可以进行取余，这样就避免了在计算过程中出现溢出的情况。

复制代码

1
2
3
4
5
6
7
res = 1;
a = a % c  //对a取余
for(int i=1; i <= b; i++){
	res = (res * a) % c; //对每一次的计算结果进行取余
}
res = res % c;

改进三：

到现在为止上述代码的时间复杂度仍然为 $O (b)$ ，下面我们对代码的时间复杂度进行改进。我们将 $b$ 的情形分为两种,如下：

$(a^2)^frac {b}{2} & ，b 为偶数\ a cdot (a^2)^frac {b-1}2 & ，b为奇数 end{cases}$

则改进的代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
res = 1;
a = a % c  //对a取余
k = (a*a) % c; //令 K = a^2
if(b%2 == 1){
	res = (res * a) mod c;  //如果是奇数，要多求一步，可以提前算到res中
}
for(int i=1; i <= b/2; i++){
	res = (res * k) % c; //对每一次的计算结果进行取余
}
res = res % c;

改进四：

我们虽然对该算法的时间复杂度做了改进，现在的时间复杂度为 $O (b / 2)$ ，但是当 $b$ 足够大时，这种写法仍然不是有效的，因此我们可以对上述代码的 for 循环进行改进。

方法就是，上述代码当第一次 for 循环时计算的是 $a^2$ ，第二次 for 循环时计算的是 $a^4$ ，之后为 $a^6$ 、 $a^8$ 、 $a^{2k}$ …… (k=1,2…… b/2 )

我们可以使用迭代的方式来替换，如 $a^2$ 、 $a^4$ 、 $a^8$ 、 $a^{2^n}$ ……

改进代码如下：

复制代码

1
2
3
4
5
6
7
8
9
res = 1;
a = a % c; 
while(b > 0){
	if (b%2 ==1 ) res = (res*a) mod c;
	a = (a*a) mod c;
	b = b/2;
}
return res;

通过以上的改进，我们的时间复杂度变为了 $log_2b$ ，以上就是快速幂求余算法。

最后

以上就是知性人生最近收集整理的关于快速幂求余算法的全部内容，更多相关快速幂求余算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Data Structure and Algorithm
浏览次数：71 次浏览
发布日期：2024-08-13 12:00:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_fw_14__23_gy.html

快速幂求余算法