快速幂全知识点
一、快速幂核心优化逻辑
核心：通过底数自乘复用中间结果，替代重复乘法运算，将时间复杂度从O(n)（暴力算法）降至O(logₖn)（快速幂）；二进制、三进制、十进制快速幂优化逻辑一致，差异仅在于指数拆分基底与底数自乘方式。
1. 暴力算法
计算 $a^{10}$ 需连续执行10次a的乘法运算，即 $a \times a \times \dots \times a$ （共10次乘法）。
痛点：乘法次数与指数b相等，高指数场景效率低下；存在冗余计算（如计算 $a^4$ 时，已计算的 $a^2$ 未被复用）。
2. 所有进制快速幂的统一优化逻辑
核心数学基础： $a^{m+n} = a^m \times a^n$ 。优化逻辑分三步，结合三种进制具体说明：
- 指数拆分：将指数b拆分为对应进制基底的幂次和，非零项数量决定乘法次数，非零项越少，乘法次数越少。
-
二进制（基底2）： $10 = 2^3 + 2^1$ ， $a^{10}=a^8 \times a^2$ （2次乘法）；
-
三进制（基底3）： $10 = 3^2 + 3^0$ ， $a^{10}=a^9 \times a^1$ （2次乘法）；
-
十进制（基底10）： $10 = 10^1$ ， $a^{10}=a^{10}$ （1次乘法）。
- 底数自乘：拆分后所需小幂次，通过底数迭代自乘获取，避免冗余计算。
-
二进制：自乘（平方）， $a \to a^2 \to a^4 \to a^8$ （3次自乘）；
-
三进制：自乘（立方）， $a \to a^3 \to a^9$ （2次自乘）；
-
十进制：自乘（10次方）， $a \to a^{10}$ （9次自乘）。
- 取模：a、b较大时，自乘结果易溢出，每步自乘、乘法后均需执行取模操作，不改变最终结果，适用于所有进制。
3. 优化效果对比
| 运算方式 | 计算 $a^{10}$ 步骤 | 总运算次数 | 复杂度 |
|---|---|---|---|
| 暴力 | a×a×a×a×a×a×a×a×a×a（10次乘） | 10次 | O(n) |
| 二进制快速幂 | 自乘3次（a→a²→a⁴→a⁸）；乘法1次（a⁸×a²） | 4次 | O(log₂n) |
| 三进制快速幂 | 自乘2次（a→a³→a⁹）；乘法1次（a⁹×a） | 3次 | O(log₃n) |
| 十进制快速幂 | 自乘9次（a→a¹⁰）；乘法0次 | 9次 | O(log₁₀n) |
结论：所有进制快速幂均通过“指数拆分+底数自乘”实现优化，差异仅在于拆分基底（2、3、10）；基底越小，底数自乘操作越简单，总运算次数越少，二进制快速幂优化效率最优。
二、不同进制快速幂底层差异
| 对比维度 | 二进制 | 三进制 | 十进制 |
|---|---|---|---|
| 拆分基底 | 2的幂 | 3的幂 | 10的幂 |
| 底数自乘方式 | 平方（1次自乘） | 立方（2次自乘） | 10次方（9次自乘） |
| 优化效率 | 最高，自乘简单、冗余最少 | 中等，自乘复杂、少量冗余 | 最低，自乘最复杂、冗余多 |
三、C++代码实现
#include <iostream>
using namespace std;
// 二进制快速幂
long long binpow(long long a, long long b, long long mod) {
long long res = 1;
a = a % mod;
while (b > 0) {
if (b & 1) {
res = (res * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return res;
}
// 三进制快速幂
long long pow_ternary(long long a, long long b, long long mod) {
long long res = 1;
long long base = a % mod;
while (b > 0) {
int digit = b % 3;
for (int i = 0; i < digit; ++i) {
res = (res * base) % mod;
}
long long new_base = 1;
for (int i = 0; i < 3; ++i) {
new_base = (new_base * base) % mod;
}
base = new_base;
b = b / 3;
}
return res;
}
// 十进制快速幂
long long pow_decimal(long long a, long long b, long long mod) {
long long res = 1;
long long base = a % mod;
while (b > 0) {
int digit = b % 10;
for (int i = 0; i < digit; ++i) {
res = (res * base) % mod;
}
long long new_base = 1;
for (int i = 0; i < 10; ++i) {
new_base = (new_base * base) % mod;
}
base = new_base;
b = b / 10;
}
return res;
}
int main() {
cout << binpow(2, 10, 1e18) << endl;
cout << pow_ternary(2, 10, 7) << endl;
cout << pow_decimal(2, 123, 1000) << endl;
return 0;
}四、取模运算核心
快速幂核心应用为计算 $a^b \mod \text{mod}$ ，基于以下取模公式，相关证明如下：
1. 核心公式
-
加法取模：(a + b) % p = (a % p + b % p) % p
-
乘法取模：(a × b) % p = [(a % p) × (b % p)] % p
-
幂取模：(a^b) % p = [(a % p)^b] % p
2. 公式严谨证明
基于带余除法：任意整数a可表示为a = q×p + r（q为商，0≤r<p，r = a%p）。
（1）加法取模公式证明
-
设a = q₁×p + r₁（r₁=a%p），b = q₂×p + r₂（r₂=b%p）；
-
a+b = (q₁+q₂)×p + (r₁+r₂)，(q₁+q₂)×p mod p = 0；
-
结论：(a+b)%p = (r₁+r₂)%p = (a%p + b%p)%p。
（2）乘法取模公式证明
-
设a = q₁×p + r₁，b = q₂×p + r₂；
-
a×b = q₁q₂p² + q₁r₂p + q₂r₁p + r₁r₂，前三项mod p = 0；
-
结论：(a×b)%p = (r₁×r₂)%p = [(a%p)×(b%p)]%p。
（3）幂取模公式证明
-
设a = q×p + r（r = a%p），二项式展开： $(x+y)^n = \sum_{k=0}^{n} C_n^k x^{n-k} y^k$ ；
-
代入得 $a^b = (qp + r)^b = \sum_{k=0}^{b} C_b^k (qp)^{b-k} r^k$ ，除 $r^b$ 外均含p因子，mod p = 0；
-
结论：(a^b)%p = r^b %p = [(a%p)^b]%p。
3. 取模细节
关键说明1
初始执行 $a = a \mod \text{mod}$ ：① 依据幂取模公式，提前取模不改变最终结果；② 将a压缩至[0, mod-1]区间，避免底数平方运算溢出。
关键说明2
每步乘法/平方后取模：多次自乘后数值易溢出，取模可将数值限制在[0, mod-1]区间，防溢出且不改变结果。
关键说明3
仅最后取模不可行：大指数下 $a^b$ 会溢出致数值异常，最终取模无意义。
五、复习小结
-
核心优化：基于 $a^{m+n}=a^m \times a^n$ ，通过指数拆分与底数自乘，将时间复杂度从O(n)降至O(logₖn)；
-
进制差异：拆分基底越小，底数自乘越简单，优化效率越高，二进制最优；
-
取模关键：牢记三条取模公式，初始、乘法、平方运算后均需执行取模操作；
-
易错点：遗漏初始取模、未及时取模、混淆不同进制的底数自乘方式。
（注：文档部分内容可能由 AI 生成）