快速幂本身无需数组，但可预存a^(2ⁱ) mod m的中间结果于数组中以支持多次查询；数组按i索引存2ⁱ次幂值，预处理O(log n)，每次查询O(log n)查表相乘。
Java 中快速幂算法本身不需要数组来实现，但若需记录每次幂运算的中间结果（比如用于调试、回溯、多级缓存或后续组合计算），可用数组高效存储这些值。关键不是“用数组加速快速幂”，而是“在快速幂过程中，用数组记录中间幂次对应的结果，便于复用或分析”。
明确数组的作用：存 2⁰, 2¹, 2², ..., 2ᵏ 对应的 a^(2ⁱ) mod m
标准快速幂按二进制位拆分指数，每次平方底数并条件乘入结果。若提前将 a²⁰, a²¹, a²², ..., a²ᵏ（k 为指数二进制位数）全部算出并存入数组，后续对任意指数 n 的幂运算，只需按 n 的二进制位查表相乘——这适合多次查询同一底数 a、不同指数 n 的场景。
- 数组长度 = ⌊log₂(n_max)⌋ + 1，其中 n_max 是你预估的最大指数
- 索引 i 存储的是 a^(2ⁱ) mod m，可一次性预处理完成
- 后续每次幂运算变为 O(log n) 次查表 + 乘法，避免重复平方
预处理数组：自底向上递推填充
利用关系 a^(2ⁱ) = (a^(2ⁱ⁻¹))² mod m，从 i=0 开始迭代计算：
long[] pow2 = new long[maxExpBits]; // maxExpBits ≈ 64 for long
pow2[0] = a % m; // a^1
for (int i = 1; i < pow2.length; i++) {
pow2[i] = (pow2[i-1] * pow2[i-1]) % m;
}注意：模运算必须每步进行，防止 long 溢出；若 a 或 m 接近 Long.MAX_VALUE，建议用 BigInteger 或自定义大数模乘。
立即学习“Java免费学习笔记（深入）”；
查表计算 a^n mod m：按 n 的二进制位累乘
遍历 n 的每一位（从低位到高位），若第 i 位为 1，则乘入 pow2[i]：
long result = 1;
int bitPos = 0;
long temp = n;
while (temp > 0) {
if ((temp & 1) == 1) {
result = (result * pow2[bitPos]) % m;
}
bitPos++;
temp >>= 1;
}该过程不依赖递归或栈，空间固定，且 pow2 数组可复用于多个不同 n 的查询——真正体现“中间结果存储以加速”的价值。
适用场景与注意事项
- 适合：底数 a 和模数 m 固定，需频繁计算 aⁿ mod m（n 变化）；或需分析各 2ⁱ 次幂行为（如密码学教学、算法可视化）
- 不适合：单次快速幂、a/m 频繁变化、内存受限嵌入式环境
- 安全提示：若用于密码学，注意侧信道（如查表访问时间差异），生产环境建议使用恒定时间实现
- 扩展：数组可改为 HashMap
存稀疏幂次，或用 List 动态扩容应对未知最大指数
