算 2 的 100 次方，逐个乘要 99 次，快速幂只要 7 轮——因为每轮「平方一下」，幂次就翻倍！
想象一个翻倍的跳远：你一次只能跳 1 米，但每跳完一次，下一次的跳远距离可以翻倍：1 米 → 2 米 → 4 米 → 8 米 → 16 米……要覆盖 13 米怎么办？别傻跳 13 次：取 8 + 4 + 1 = 13——跳 3 次「翻倍」得到 8 米和 4 米的能力，再拼上起步的 1 米，搞定。
算幂次也是同一招！算 2¹³：别连乘 12 次，先「平方」得到 2² → 2⁴ → 2⁸（只平方 3 次），再用 13 = 8 + 4 + 1 拼起来：2¹³ = 2⁸ × 2⁴ × 2¹。每一步平方都把「能表示的指数」翻倍，所以指数再大，轮数也只是指数的二进制位数——这就是倍增法。
两条基本规律（后面全靠它们）：a^(x+y) = a^x × a^y（指数相加 → 幂相乘）；a^(2x) = (a^x)²（指数翻倍 → 平方一下就行）。
算 2¹⁰⁰，最直白的办法是连乘：2 × 2 × 2 × … × 2（100 个 2），要做 99 次乘法。指数是 b，就要 b−1 次乘法——这叫 O(n)（线性：指数多大，步数就多大）。
// 逐个乘（朴素算法）：每步乘一次底数 2^1 = 2 2^2 = 2 × 2 // 1 次乘法 2^3 = 2 × 2 × 2 // 2 次乘法 2^10 = 2 连乘 9 次 // 9 次乘法 2^100 = 2 连乘 99 次 // 99 次乘法——还行 // 但指数是 10^8（一亿）时呢？ 2^(10^8) = 2 连乘 99999999 次 // 一亿次！每秒 10^8 次也要 1 秒， // 慢一点的机器就是「卡死」 // 目标：把 b−1 次乘法，降到「log₂ b 量级」的轮数
关键观察：平方一下，指数就翻倍。2² 平方一下 = (2²)² = 2⁴；2⁴ 平方一下 = 2⁸；2⁸ 平方一下 = 2¹⁶……所以「2 的 2 的幂次方」可以链式免费得到：
// 翻倍链：每步一次平方，指数 ×2 2^1 = 2 2^2 = (2^1)² = 4 // 1 次平方 2^4 = (2^2)² = 16 // 第 2 次平方 2^8 = (2^4)² = 256 // 第 3 次平方 2^16 = (2^8)² = 65536 // 第 4 次平方 // 算 2^13？13 不是 2 的幂，但 13 = 8 + 4 + 1： 2^13 = 2^(8+4+1) = 2^8 × 2^4 × 2^1 = 256 × 16 × 2 = 8192 // 只用：3 次平方 + 2 次「拼」乘法 = 5 次（逐个乘要 12 次） // 更大的：2^100 = (2^50)² = ((2^25)²)² …… 指数 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1 // 反过来读：从 2^1 起步，平方 7 次就能「够到」2^100 的规模， // 再按 100 = 64 + 32 + 4（二进制 1100100）把对应的几块乘起来。 // 为什么拆成 8 + 4 + 1？因为 13 的二进制是 1101： // 13 = 1×8 + 1×4 + 0×2 + 1×1 → 哪一位是 1，就乘哪一块
把「翻倍链 + 按位拼」写成固定动作，每轮做三件事：① 指数的最低位是 1？是 → 结果 ×= 底数；② 底数平方；③ 指数 ÷ 2（取整）。指数变 0 就停。
// 快速幂（迭代版）伪代码：算 a^b res = 1 // 结果，先放 1（乘法的起点） while b > 0: 若 b 是奇数: res = res × a // 最低位是 1 → 乘进当前这块 a = a × a // 底数平方 → 下一块指数翻倍 b = b ÷ 2（取整） // 指数右移一位 return res // 手推 2^13（13 的二进制 = 1101，从低位看起：1、0、1、1） 轮 b(本轮开始) 奇? 本轮后 res 平方后 a 0 13 是 1×2 = 2 2 → 4 1 6 否 2 4 → 16 2 3 是 2×16 = 32 16 → 256 3 1 是 32×256 = 8192 256 → 65536 b = 0，停 → 2^13 = 8192 ✓（2^13 = 8192 验证过） // 一共 4 轮，乘法共 7 次：4 次「平方」+ 3 次「乘进 res」（第 0、2、3 轮） // 逐个乘要 12 次 → 指数越大，优势越明显！ // 对照二进制：13 = 1101，最低位起依次是 1、0、1、1 // 位是 1 的轮（第 0、2、3 轮）各乘进一块：2^1、2^4、2^8 // res = 2^1 × 2^4 × 2^8 = 2^13 —— 正是 13 = 1 + 4 + 8
每轮 b ÷ 2，b 从「一亿」变「一」要多少次？就是二进制位数：
// b 每轮减半：轮数 = 把 b 写成二进制的位数 b = 13 → 1101₂ 4 位 → 4 轮（子任务 3 数过 ✓） b = 100 → 1100100₂ 7 位 → 7 轮（log₂100 ≈ 6.64，进一 7） b = 10^8 → 二进制 27 位 → 27 轮 （2^26 = 67108864 < 10^8 < 2^27 = 134217728） // 对比（b = 10^8）： 逐个乘：99999999 次乘法 // O(n)：一亿次 快速幂：27 轮（每轮 1 次平方 + 至多 1 次乘） // O(log n)：27 轮！ // 「log」的直觉：10^8 看着很大，但「减半次数」很小—— // 1亿 → 5千万 → 2500万 → … → 1，数一数：27 步就到底 // 所以指数再大（10^18？），快速幂也只要 ~60 轮
// 输入：a b（2 ≤ a ≤ 10，0 ≤ b ≤ 60，答案用 long long 防溢出） // 输出：a^b（快速幂结果）+ 快速幂轮数 vs 逐个乘次数 // 示例：2 13 → 8192（4 轮 vs 12 次） // 3 5 → 243（3 轮 vs 4 次） // 2 0 → 1（0 轮 vs 0 次） #include <iostream> using namespace std; long long fastpow(long long a, int b) { long long res = 1; // 结果从 1 开始（乘法的起点） while (b > 0) { if (b % 2 == 1) // 最低位是 1：乘进当前这块 res *= a; a *= a; // 平方：下一块指数翻倍 b /= 2; // 指数减半（右移一位） } return res; } int main() { long long a; int b; cin >> a >> b; int rounds = 0; // 快速幂轮数 = b 的二进制位数 for (int t = b; t > 0; t /= 2) rounds++; cout << a << "^" << b << " = " << fastpow(a, b) << endl; cout << "快速幂 " << rounds << " 轮，逐个乘 " << b << " 次乘法" << endl; return 0; } // 动手验证：输入 2 13 → 8192（4 轮 vs 12 次） // 输入 7 20 → 79792266297612001（5 轮 vs 19 次） // 输入 10 18 → 1000000000000000000（5 轮 vs 17 次）