当前位置：网站首页 > 文章教程 > 正文

C++数据结构:快速幂

xsobi 2024-11-23 10:51 12 浏览

朴素的求幂算法

也就是平常使用pow函数，最简单的实现就是一直累乘，可以得到这样的代码：

可以看到，算法的时间复杂度是O(n)。为了降低时间复杂度，我们可以使用快速幂算法，将时间复杂度降低到O(logn)，n是幂。

快速幂

关于快速幂，博主的理解是使用位运算。下面是数学证明：

关于a^b，举一个实际的例子——2^10。

那么对于6而言，如果我们将10变成二进制，那么就是：1010，如果变成加权的情况可以得到表达式：

0*2^0 + 1*2^1 + 0*2^2 + 1*2^3

代入原来的2^10可以得到表达式：

2^(0*2^0 + 1*2^1 + 0*2^2 + 1*2^3)

然后再拆开并化简这个表达式，可以得到：

2^(2^1) * 2^(2^3)

也就是说，我们在求解2^10的时候，可以考虑成根据二进制的权值来求解的。那么在关于位运算的部分，我们可以逐位获取b的位，碰到0，就累乘，碰到1，就将累乘的值乘到答案。由此可以得到代码：

关于位运算的部分，这里只简单提一下，更多详细内容请百度。if语句中的b & 1，也就是将b与1按位与，那么1的二进制是1，也就是说b除了最后一位，其他位都和0相与，那么得到的值一定都是0。而最后一位与上1，那么原来位实际上是不变的。这样我们就获得了b的最后一位的值。while循环中b >>= 1，是移位运算，将b向右移动1位。因为每次我们都是要获取最后一位，看是0还是1，那么每次移动1位，下一次在碰见if语句，就得到原来最后一位的前一位了。

核心代码是下面这一部分：

博主理解这里理解半天Orz，这里其实是对上面一句话的模拟：“2^(2^1) * 2^(2^3)”。实际操作一下吧：

可以看到，出现0的时候，我们就累乘，得到的是幂的累积值。出现1的时候，我们将累积的幂值进行累乘。或者说碰见一个1，就出现一次底数2。

如果仍然没有太理解，debug一下会有很多帮助。

快速幂取模
这一部分就跟数论关系很大了。取模也是数论问题中经常出现的。那么对于幂来取模，如果我们直接用模运算实际上是速度很慢的（因为试除法）。所以我们不妨在求快速幂的时候添加一些内容，从而得到结果。这个算法需要了解一下数论的一个定理：

(a*b) mod c = ((a mod c)*(b mod c)) mod c

那么根据上面的定理可以推导出另一个定理：

(a^b) mod c = (a mod c)^b mod c

具体的证明这里不再赘述，主要是看第二个定理，恰好符合我们的小标题——快速幂取模。我们可以在求快速幂的时候，通过对底数取模的方式，不断缩小底数的规模。那么我们在上面快速幂的基础上，添加取模，就可以完成整个操作。

如果能理解上面的快速幂算法，那么这个也会比较好理解了。定理里面，底数是要有一次取模运算的。这里我们在给base赋值的时候就运行了一次。那么对于后面的一次取模，我们实际上利用了分配率，即：

(a*b) mod c = ((a mod c)*(b mod c)) mod c

我们求幂的本质仍然是求积。所以每次我们对base或者ans进行运算的时候，都必须使用一次分配率，所以都要mod c。

总结

在这里为大家准备了做算法题时的代码模板，是yxc大佬的总结，希望对大家有帮助：

希望大家点赞三连[灵光一闪]

移位运算

上一篇：集合框架知识
下一篇：《Java编程思想》第五版:第四章运算符

C++数据结构:快速幂

朴素的求幂算法

快速幂

总结

相关推荐

「猪译馆」ASFV在不同基质中的存活时间(一)

2022年Android面试题及答案收集(不断更新中)

63.C# ListView控件 c#listview控件用法

同样的面试题，Android的答案和Java不一样

ESP32/8266开发环境超详细安装步骤

在C#中，文件的创建、最后访问和最后修改时间是如何存储和管理的

springboot整合mybatis使用xml实现sql语句的查询配置

HTML中的标签 html中的标签用于什么

网页布局技巧（网页布局技巧有）

史上硬核!Jar 包依赖冲突排查思路和解决方法

C++数据结构:快速幂

朴素的求幂算法

快速幂

总结

微信扫一扫：分享

相关推荐

「猪译馆」ASFV在不同基质中的存活时间(一)

2022年Android面试题及答案收集(不断更新中)

63.C# ListView控件 c#listview控件用法

同样的面试题，Android的答案和Java不一样

ESP32/8266开发环境超详细安装步骤

在C#中，文件的创建、最后访问和最后修改时间是如何存储和管理的

springboot整合mybatis使用xml实现sql语句的查询配置

HTML中的标签 html中的标签用于什么

网页布局技巧（网页布局技巧有）

史上硬核!Jar 包依赖冲突排查思路和解决方法