【每日算法Day 84】超级次方

LeetCode 372. 超级次方 (opens new window)

题目描述

你的任务是计算 a的b次方 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例

输入: a = 2, b = [1,2]
输出: 4096

解题思路

在b很大的时候，尝试直接表示b都有可能整型溢出，而题目要求的是最终取模的结果，我们可以用模运算的性质(a*b)%c=((a%c)*(b%c))%c在计算过程中控制数值不溢出。由于求b次方的过程就是多个a相乘的过程，那么可以用到该模运算性质。

另外，以2^112为例，2^112 = 2^2 * 2^110 = 2^2 * (2^11)^10，这样就把表示B的数组长度减小了，出现了递归子问题。在递归过程中求10次以内的幂时每次乘都用上面的模运算性质保证结果正确且不溢出。

public class No372_SuperPow {
    private final int MODULUS = 1337;

    public int superPow(int a, int[] b) {
        if (b == null || b.length == 0 || a == 0) return 0;
        return superPow(a, b, b.length - 1);
    }

    //高位的结果的10次方乘低位的结果再取模
    private int superPow(int a, int[] b, int lowBit) {
        if (lowBit < 0) return 1;
        int lowPow = getPow(a, b[lowBit]);
        int highPow = getPow(superPow(a, b, lowBit - 1), 10);
        return (lowPow * highPow) % MODULUS;
    }

    //计算10次以内的幂函数
    private int getPow(int base, int exponent) {
        if (exponent == 0) return 1;
        base %= MODULUS;
        if (exponent == 1) return base;
        int sqrt = getPow(base, exponent >> 1);
        //每一步乘完都要取模，否则可能溢出
        int result = (sqrt * sqrt) % MODULUS;
        //根据指数的奇偶性返回结果，类似俄罗斯农民乘法，不过在指数不超过10的情况下优化效果有限
        if ((exponent & 1) == 1)
            return (base * result) % MODULUS;
        else
            return result;
    }
}