跳至主要內容

 

labuladong约 840 字大约 3 分钟递归数学

Info

数据结构精品课open in new window递归算法专题课open in new window 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》open in new window 出版,签名版限时半价!

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
372. Super Powopen in new window372. 超级次方open in new window🟠

今天来聊一道与数学运算有关的题目,力扣第 372 题「超级次方open in new window」,让你进行巨大的幂运算,然后求余数。

int superPow(int a, vector<int>& b);

要求你的算法返回幂运算 a^b 的计算结果与 1337 取模(mod,也就是余数)后的结果。就是你先得计算幂 a^b,但是这个 b 会非常大,所以 b 是用数组的形式表示的。

这个算法其实就是广泛应用于离散数学的模幂算法,至于为什么要对 1337 求模我们不管,单就这道题可以有三个难点:

一是如何处理用数组表示的指数,现在 b 是一个数组,也就是说 b 可以非常大,没办法直接转成整型,否则可能溢出。你怎么把这个数组作为指数,进行运算呢?

二是如何得到求模之后的结果?按道理,起码应该先把幂运算结果算出来,然后做 % 1337 这个运算。但问题是,指数运算你懂得,真实结果肯定会大得吓人,也就是说,算出来真实结果也没办法表示,早都溢出报错了。

三是如何高效进行幂运算,进行幂运算也是有算法技巧的,如果你不了解这个算法,后文会讲解。

那么对于这几个问题,我们分开思考,逐个击破。

本文剩余内容为会员内容,请先购买 网站会员 open in new window ,然后 借助 Chrome 插件解锁网页 open in new window 或者 点这里open in new window 跳转小鹅通查看。

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释