力扣：快速幂问题总结（50、372）

谁借莪１个温暖的怀抱￠ 2023-01-19 03:29 18阅读 0赞

# 一、计算 a n a^n an的3种方法 #

## 1.累乘法（不推荐） ##

double res = 1.0;
    while(n-- > 0) {
        
    	res *= a;
    }

> 时间复杂度：O(n)；  
> 乘法运算本身就耗时，所以这种方式不适合用于刷力扣题。

## 2.快速幂（二进制取幂） ##

(1)思路  
①等价变换： 5 13 = 5 ( 1101 ) 2 = 5 1 ⋅ 2 0 + 0 ⋅ 2 1 + 1 ⋅ 2 2 + 1 ⋅ 2 3 = 5 1 ⋅ 2 0 ⋅ 5 0 ⋅ 2 1 ⋅ 5 1 ⋅ 2 2 ⋅ 5 1 ⋅ 2 3 5^\{13\} = 5^\{(1101)\_2\} = 5^\{1·2^0+0·2^1+1·2^2+1·2^3\}=5^\{1·2^0\}·5^\{0·2^1\}·5^\{1·2^2\}·5^\{1·2^3\} 513=5(1101)2=51⋅20\+0⋅21\+1⋅22\+1⋅23=51⋅20⋅50⋅21⋅51⋅22⋅51⋅23  
②规律：  
 5 2 1 = ( 5 2 0 ) 2 5^\{2^1\}=(5^\{2^0\})^2 521=(520)2  
 5 2 2 = ( 5 2 1 ) 2 5^\{2^2\}=(5^\{2^1\})^2 522=(521)2  
 5 2 3 = ( 5 2 2 ) 2 5^\{2^3\}=(5^\{2^2\})^2 523=(522)2

(2)应用场景  
求 a n a^n an，a既可以是整数，也可以是浮点数；但必须保证容易将n转化为二进制的形式。

(3)力扣题：[50. Pow(x, n)][50. Pow_x_ n]

*  AC代码

class Solution {
        
        public double myPow(double x, int n) {
        
            if(Math.abs(x - 1) == 0) return (double)1;
            boolean flag = n < 0 ? true : false;
            long N = n;
            if(N < 0) N = -N; 
            double base = x;
            double res = 1;
            while(N != 0) {
        
                if(N % 2 == 1)
                    res *= base;
                base *= base;
                N >>= 1;
            }
            return flag == true ? 1 / res : res;
        }
    }

> 细节：  
> ①因为n能取到 − 2 31 -2^\{31\} −231，所以一旦取反，则溢出了。故要用long型的N来存储。（**这个坑很常见，小伙伴们别踩了！**）  
> ![在这里插入图片描述][20210507184438775.png]  
> ②1的任何次幂都为1  
> ![在这里插入图片描述][20210507184920678.png]

> `快速幂算法`：  
> ![在这里插入图片描述][20210507185015142.png]  
> ①`double base = x;`相当于 5 2 0 5^\{2^0\} 520  
> `base *= base;`相当于 5 2 1 = ( 5 2 0 ) 2 5^\{2^1\}=(5^\{2^0\})^2 521=(520)2  
> ② 5 13 = 5 ( 1101 ) 2 = 5 1 ⋅ 2 0 + 0 ⋅ 2 1 + 1 ⋅ 2 2 + 1 ⋅ 2 3 = 5 1 ⋅ 2 0 ⋅ 5 0 ⋅ 2 1 ⋅ 5 1 ⋅ 2 2 ⋅ 5 1 ⋅ 2 3 5^\{13\} = 5^\{(1101)\_2\} = 5^\{1·2^0+0·2^1+1·2^2+1·2^3\}=5^\{1·2^0\}·5^\{0·2^1\}·5^\{1·2^2\}·5^\{1·2^3\} 513=5(1101)2=51⋅20\+0⋅21\+1⋅22\+1⋅23=51⋅20⋅50⋅21⋅51⋅22⋅51⋅23  
> 二进制位为0时，如 5 0 ⋅ 2 1 = 1 5^\{0·2^1\} = 1 50⋅21=1,所以：  
> ![在这里插入图片描述][20210507185506791.png]

## 3. 递归法 ##

(1)递归式  
 a n = \{ a ∗ a n − 1 ， n 为 奇 数 ( a n 2 ) 2 ， n 为 偶 数 a^n=\\left\\\{ \\begin\{array\}\{lr\} a \* a^\{n - 1\}，n为奇数 \\\\ (a^\{\\frac\{n\}\{2\}\})^2，n为偶数 \\end\{array\} \\right. an=\{ a∗an−1，n为奇数(a2n)2，n为偶数  
(2)应用场景：当n不便于转化为二进制形式时

(3)力扣题：[372. 超级次方][372.]

*  说明  
    本题的解题思路来源于：东哥（`labuladong`）
 *  AC代码

class Solution {
        
        private final int num = 1337;
        public int superPow(int a, int[] b) {
        
            return myPow(a, b, b.length - 1);  
        }
        private int myPow(int a, int[] b, int index) {
        
            if(index < 0) return 1;
            int part1 = quickPow(a, b[index]) % num;
            index--;
            int part2 = quickPow(myPow(a, b, index), 10) % num;
            return (part1 * part2) % num; 
        }
    
        private int quickPow(int base, int exp) {
        
            if(exp == 0) return 1;
            base %= num;
            if(exp % 2 == 0) {
        
                int tmp = quickPow(base, exp >> 1);
                return (tmp * tmp) % num;
            }
            else
                return (base * quickPow(base, exp - 1)) % num;
        }
        
    }

> 核心思路：幂运算的规律  
>  a \[ 1 , 5 , 6 , 4 \] = a 4 ∗ a \[ 1 , 5 , 6 , 0 \] = a 4 ∗ ( a \[ 1 , 5 , 6 \] ) 10 a^\{\[1,5,6,4\]\} = a^4 \* a^\{\[1,5,6,0\]\} = a^4 \* (a^\{\[1,5,6\]\})^\{10\} a\[1,5,6,4\]=a4∗a\[1,5,6,0\]=a4∗(a\[1,5,6\])10  
> 将 a \[ 1 , 5 , 6 , 4 \] a^\{\[1,5,6,4\]\} a\[1,5,6,4\]分成2部分来求：① a 4 a^4 a4；② ( a \[ 1 , 5 , 6 \] ) 10 (a^\{\[1,5,6\]\})^\{10\} (a\[1,5,6\])10，其中对于 a \[ 1 , 5 , 6 \] a^\{\[1,5,6\]\} a\[1,5,6\]又可以继续分成2部分来求解，即`递归求解`。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]

> **递归法**求 a n a^n an  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]

> 模运算的知识：`(a * b) % p = ((a % p) * (b % p)) % p`

# 二、尾声 #

如果小伙伴们读完本篇博客觉得有所收获的话，还望多多点赞收藏哟，也欢迎小伙伴们在评论区留下宝贵的评论，比心。

[50. Pow_x_ n]: https://leetcode-cn.com/problems/powx-n/
[20210507184438775.png]: /images/20221021/5181e9bf6875441eb17d9668c40df800.png
[20210507184920678.png]: /images/20221021/f6ac3325c7fd4f4fb26f2cc7c87ef1d3.png
[20210507185015142.png]: /images/20221021/002019ef412f4400800618fd181235ce.png
[20210507185506791.png]: /images/20221021/771aa96170304fb6be8a935415eca39d.png
[372.]: https://leetcode-cn.com/problems/super-pow/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20221021/d0ff03e67fc3485d88eb7336baebee1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/fab968f67e73434cad2e500664072d7e.png