快速幂法

作者：Liew.Y
先上代码后面解释

#include <cstdio>

int main(void) {
    // 快速幂法
int base = 2;  // 底数2
int power = 14;  // 指数n
int result = 1;  // 结果
    while (power) {
        if (power & 1) {
            result *= base;
        }
        base *= base;
        power >>= 1;
    }
    printf("%d", result);
    return 0;
}

什么是快速幂法？

其本质就是把幂不断降次。
如： $2^{12}_{(10)} = 4^{6}_{(10)}$

这个时候我们需要思考一个问题

幂运算的本质是什么？

其本质就是连续的乘法

这个时候我们又要思考一个问题
如何把降幂运算和计算机结合？

$$\begin{aligned} &\textbf{思维链}\\[4pt] 1. &\text{ 首先计算机运算以及数据储存的形式是\textbf{二进制}}\\[4pt] 2. &\text{ 其次二进制每一位储存的形式是 }2^{n}\\[4pt] 3. &\text{ 而 } \text{base} \times \text{base}= \text{base}^{2}\\[4pt] 4. &\text{ 所以我们可以得到一个简单的思路}\\[4pt] 5. &\text{ 所有的 }n_{(10)}\text{ 都可以使用二进制形式 }n_{(2)}\text{ 来进行表示}\\[4pt] 6. &\text{ 对于 } \text{base}^{\text{power}} = \text{base}^{2^{n}+2^{n-1}+\dots+2^{0}}\\[4pt] 7. &\text{ 最终我们可以得到 } \text{base}^{\text{power}}=\text{base}^{2^{n}}\cdot \text{base}^{2^{n-1}}\cdot \dots \cdot \text{base}^{2^{0}}\\[4pt] 8. &\text{ 我们还可以观察到 } \text{base}^{2^{n}}=\text{base}^{2^{n-1}}\cdot \text{base}^{2^{n-1}} = (\text{base}^{2^{n-1}})^{2}\\[8pt] &\boxed{\text{结果：以 }\text{base}^{2}\text{ 为基础不断降幂}} \end{aligned}$$

此时我们自然的想到

if 存在2的某次方对应的位数为0 {
	不应该相乘
} else {
	相乘
}
进入下一位

此时我们产生了一个问题：
如何确定是否要相乘？

$$\begin{aligned} &\textbf{思维链}\\[4pt] 1. &\text{ 计算机以二进制存储数据。}\\[4pt] 2. &\text{ 降幂本质：}\quad \text{base}^{2k}= (\text{base}^{k})^{2} = \text{base}^{k}\cdot \text{base}^{k} \\[4pt] 3. &\text{ 二进制位不连续，如 }1001_{(2)}\\[4pt] 4. &\text{ 仅需判断“当前位是否为 }1\text{”} \Rightarrow \text{真假}\\[4pt] 5. &\text{ 不关心原值是否被破坏。}\\[6pt] 6. &\text{ 做法：}\\ &\quad\text{power} \& 1 \quad\text{(取最低位)}\\ &\quad\text{power} \gg 1 \quad\text{(右移一位，丢弃已处理位)}\\[6pt] &\boxed{\text{借助 }0000\,0001_{(2)}\text{ 逐位取值}} \end{aligned}$$

此时我们已经可以写出代码

#include <cstdio>

int main(void) {
int base = 3;
int power = 5, result = 1;
    while (power) {
        if (power & 1) {
            result *= base;
        }
        base *= base;
        power >>= 1;
    }
    printf("%d", result);
    return 0;
}

进阶–递归法

long long fastPow(long long a, long long b) {
    if (b == 0) return 1;//截止条件
    long long half = fastPow(a, b/2);//递归基
    return (b % 2) ? half * half * a : half * half;//结果整合
}

递归解析

递归，递归，递归

• Liew.Y

众所周知递归是很难理解的，所以针对递归我进行详细解释：其实是我不会

$$\begin{aligned} &\textbf{Step1} \quad\text{从“分-治-合”的角度分析}\\[6pt] \textbf{分} &: \text{把指数 }b\text{ 不断二分}\\ &\quad\text{快速幂的降幂基础：} \mathbf{base^{b}} = (\mathbf{base^{b/2}})^{2}\\[4pt] \textbf{治} &: \text{计算子问题}\\ &\quad\mathbf{\text{base}^{b} = \text{base}^{b/2} \cdot \text{base}^{b/2}}\\[4pt] \textbf{合} &: \text{整合子结果}\\[4pt] \text{若 b 为奇数}&: \mathbf{\text{base}^{b} = \text{base}^{b/2} \cdot \text{base}^{b/2} \cdot \text{base}}\\[4pt] \text{若 b 为偶数}&: \mathbf{\text{base}^{b} = \text{base}^{b/2} \cdot \text{base}^{b/2}}\\[6pt] \text{如何计算 }&\mathbf{\text{base}^{b/2^{n}}}\\[2pt] &\text{利用 } \mathbf{\text{base}^{0}=1}\\[6pt] \text{核心观察}&: \mathbf{\text{base}^{b} = \bigl(\text{base}^{b/2}\bigr)^{2}} \end{aligned}$$

补充部分

我们由此次观察不仅可以得到可以通过

N&1

的形式取得低位
同时也可以自然的得到另一种方法
N%2

PROVE
如果N_{(2)}=1001_{(2)}

则 N_{(10)}=2^{3}+2{0} 的形式，其中前项是偶数 => 余数=2^{0}

扩展

模下快速幂

必备知识
$(a \times b) \bmod c = ((a \bmod c) \times (b \bmod c)) \bmod c$
这里我们或许认为很难以记忆

其实确实不好理解 但是我们直接简记：层层求模

应用方法

题目
给定一个整数n求，$2^{n}$对于1007的模;

思维链

1. 首先要求幂运算，我们可以想到快速幂法
2. 其次要求模，刚好结合我们的扩展
3. 现在开始拆分
4. 首先 result = result * base
5. 我们当然第一时刻想到的是直接对最终结果求mod
6. 但是显而易见，计算机的数据储存很可能不足
7. 所以我们采用扩展的公式
8. 对result和base分别求mod
   思考结果：更改开头代码对二者分别求mod

完整代码

#include <cstdio>

int main(void) {
int base = 2;
int power, result = 1;
    scanf("%d", &power);
    while (power) {
        if (power & 1) {
            result = (result * base) % 1007;
        }
        base = (base * base) % 1007;
        power >>= 1;
    }
    printf("%d", result);
    return 0;
}

注意

虽然快速幂法相比于暴力算法更快
但是需要记住快速幂法和暴力法一样都受制于内存的限制