一、概念

二分快速幂

二、模板

请看例题2

三、例题

题：50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n^ ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104    

解：

解题思路：快速幂

快速幂（二进制解析）：

对于一个任何十进制正整数 n ，设其二进制为：“bm...b2b1”

二进制转十进制：

$$ n=2^0*b_1+2^1*b_2+\cdot \cdot \cdot +2^{m-1}*b_m $$幂的二进制展开： $$

x^n=x^{2^0b_1+2^1b_2+\cdot \cdot \cdot +2^{m-1}b_m}=x^{2^0b_1}x^{2^1*b_2}\cdot \cdot \cdot x^{2^{m-1}}

$$ *** **快速幂(二分推导)：** $$

x^n=\left{ \begin{array}{l} \left( x^2 \right) ^{n/2},\ n\text{为偶数}\\ x\left( x^2 \right) ^{n/2},\ n\text{为奇数}\\ \end{array} \right.

$$ *** AC代码： ```java class Solution { public double myPow(double x, int n) { if(x == 0.0f) return 0.0d; // 底数为0 long b = n; // 防止负数转正数溢出 if(b < 0) { b = -b; x = 1/x; } double res = 1.0; while(b > 0) { if((b & 1) != 0) res *= x; x *= x; b >>= 1; } return res; } } ``` ## 题：372. 超级次方 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。 示例 1： 输入：a = 2, b = [3] 输出：8 示例 2： 输入：a = 2, b = [1,0] 输出：1024 示例 3： 输入：a = 1, b = [4,3,3,8,5,2] 输出：1 示例 4： 输入：a = 2147483647, b = [2,0,0] 输出：1198 提示： 1 <= a <= 231 - 1 1 <= b.length <= 2000 0 <= b[i] <= 9 b 不含前导 0 ## 解： 解题思路：`快速幂` 例子： 0. a^K^ = 99^2345^ 1. 99^K^ = 99^234*10+5^ 2. 99^234*10+5^ = 99^234*10^ * 99^5^ 3. 99^234*10^ * 99^5^ = (99^234^)^10^ * 99^5^ AC代码： ```java class Solution { int MOD = 1337; public int superPow(int a, int[] b) { return dfs(a, b, b.length - 1); } int dfs(int a, int[] b, int u) { if(u == -1) return 1; return qpow(dfs(a, b, u - 1), 10) * qpow(a, b[u]) % MOD; } // 快速幂 int qpow(int a, int b) { int ans = 1; a %= MOD; while(b > 0) { if((b & 1) != 0) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } } ```