专栏首页苦逼的码农Super Pow:如何高效进行模幂运算

Super Pow:如何高效进行模幂运算

来源:labuladong

作者:labuladong

今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。

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

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

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

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

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

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

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

如何处理数组指数

首先明确问题:现在b是一个数组,不能表示成整型,而且数组的特点是随机访问,删除最后一个元素比较高效。

不考虑求模的要求,以b = [1,5,6,4]来举例,结合指数运算的法则,我们可以发现这样的一个规律:

看到这,我们的老读者肯定已经敏感地意识到了,这就是递归的标志呀!因为问题的规模缩小了:

    superPow(a, [1,5,6,4])
=>  superPow(a, [1,5,6])

那么,发现了这个规律,我们可以先简单翻译出代码框架:

// 计算 a 的 k 次方的结果
// 后文我们会手动实现
int mypow(int a, int k);

int superPow(int a, vector<int>& b) {
    // 递归的 base case
    if (b.empty()) return 1;
    // 取出最后一个数
    int last = b.back();
    b.pop_back();
    // 将原问题化简,缩小规模递归求解
    int part1 = mypow(a, last);
    int part2 = mypow(superPow(a, b), 10);
    // 合并出结果
    return part1 * part2;
}

到这里,应该都不难理解吧!我们已经解决了b是一个数组的问题,现在来看看如何处理 mod,避免结果太大而导致的整型溢出。

如何处理 mod 运算

首先明确问题:由于计算机的编码方式,形如(a * b) % base这样的运算,乘法的结果可能导致溢出,我们希望找到一种技巧,能够化简这种表达式,避免溢出同时得到结果。

比如在二分查找中,我们求中点索引时用(l+r)/2转化成l+(r-l)/2,避免溢出的同时得到正确的结果。

那么,说一个关于模运算的技巧吧,毕竟模运算在算法中比较常见:

(a*b)%k = (a%k)(b%k)%k

证明很简单,假设:

a=Ak+B;b=Ck+D

其中 A,B,C,D 是任意常数,那么:

ab = ACk^2+ADk+BCk+BD

ab%k = BD%k

又因为:

a%k = B;b%k = D

所以:

(a%k)(b%k)%k = BD%k

综上,就可以得到我们化简求模的等式了。

换句话说,对乘法的结果求模,等价于先对每个因子都求模,然后对因子相乘的结果再求模

那么扩展到这道题,求一个数的幂不就是对这个数连乘么?所以说只要简单扩展刚才的思路,即可给幂运算求模:

int base = 1337;
// 计算 a 的 k 次方然后与 base 求模的结果
int mypow(int a, int k) {
    // 对因子求模
    a %= base;
    int res = 1;
    for (int _ = 0; _ < k; _++) {
        // 这里有乘法,是潜在的溢出点
        res *= a;
        // 对乘法结果求模
        res %= base;
    }
    return res;
}

int superPow(int a, vector<int>& b) {
    if (b.empty()) return 1;
    int last = b.back();
    b.pop_back();

    int part1 = mypow(a, last);
    int part2 = mypow(superPow(a, b), 10);
    // 每次乘法都要求模
    return (part1 * part2) % base;
}

你看,先对因子a求模,然后每次都对乘法结果res求模,这样可以保证res *= a这句代码执行时两个因子都是小于base的,也就一定不会造成溢出,同时结果也是正确的。

至此,这个问题就已经完全解决了,已经可以通过 LeetCode 的判题系统了。

但是有的读者可能会问,这个求幂的算法就这么简单吗,直接一个 for 循环累乘就行了?复杂度会不会比较高,有没有更高效的算法呢?

有更高效的算法的,但是单就这道题来说,已经足够了。

因为你想想,调用mypow函数传入的k最多有多大?k不过是b数组中的一个数,也就是在 0 到 9 之间,所以可以说这里每次调用mypow的时间复杂度就是 O(1)。整个算法的时间复杂度是 O(N),N 为b的长度。

但是既然说到幂运算了,不妨顺带说一下如何高效计算幂运算吧。

如何高效求幂

快速求幂的算法不止一个,就说一个我们应该掌握的基本思路吧。利用幂运算的性质,我们可以写出这样一个递归式:

这个思想肯定比直接用 for 循环求幂要高效,因为有机会直接把问题规模(b的大小)直接减小一半,该算法的复杂度肯定是 log 级了。

那么就可以修改之前的mypow函数,翻译这个递归公式,再加上求模的运算:

int base = 1337;

int mypow(int a, int k) {
    if (k == 0) return 1;
    a %= base;

    if (k % 2 == 1) {
        // k 是奇数
        return (a * mypow(a, k - 1)) % base;
    } else {
        // k 是偶数
        int sub = mypow(a, k / 2);
        return (sub * sub) % base;
    }
}

这个递归解法很好理解对吧,如果改写成迭代写法,那就是大名鼎鼎的快速幂算法。至于如何改成迭代,很巧妙,这里推荐一位大佬的文章 让技术一瓜共食:快速幂算法

虽然对于题目,这个优化没有啥特别明显的效率提升,但是这个求幂算法已经升级了,以后如果别人让你写幂算法,起码要写出这个算法。

至此,Super Pow 就算完全解决了,包括了递归思想以及处理模运算、幂运算的技巧,可以说这个题目还是挺有意思的,你有什么有趣的题目,可以留言分享一下。

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二分搜索只能用来查找元素吗?

    最常见的就是教科书上的例子,在有序数组中搜索给定的某个目标值的索引。再推广一点,如果目标值存在重复,修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引...

    帅地
  • 面试官,求求你不要问我这么简单但又刁难的算法题了

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 阶乘很简单?恕我直言,阶乘相关的面试题你还真不一定懂!

    对于如何算 n 的阶乘,只要你知道阶乘的定义,我想你都知道怎么算,但如果在面试中,面试官抛给你一道与阶乘相关,看似简单的算法题,你还真不一定能够给出优雅的答案!...

    帅地
  • 675. Cut Off Trees for Golf Event

    You are asked to cut off all the trees in this forest in the order of tree’s he...

    用户1147447
  • 一遍记住Java常用的八种排序算法与代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    田维常
  • 力扣(LeetCode)刷题,简单题+中等题(第20期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • K-th Smallest Prime Fraction

    思路1: 一种聪明的做法,如果A = [1, 7, 23, 29, 47],那么有:

    用户1147447
  • P3808 【模版】AC自动机(简单版)

    题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

    attack
  • P3808 【模版】AC自动机(简单版)

    题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

    attack
  • 分治法(Divide-and-Conquer Algorithm)经典例子分析

    上一篇文章里给大家介绍了归并排序,今天首先给大家带来同样运用分治法来解决问题的快速排序。

    用户1621951

扫码关注云+社区

领取腾讯云代金券