为了方便你创建 OJ（Online Judge）测试数据，我编写了这个 C++ 数据生成器。它包含了标准迭代版快速幂算法作为标程（用于生成 .out 文件），并针对性地覆盖了从简单样例到极端边界的所有情况。

数据生成器逻辑设计

1. 测试点 1：官方样例数据，验证基础逻辑。
2. 测试点 2-3：边界特判。包含 $b=0$（指数为0）和 $p=1$（任何数模1等于0）的情况。
3. 测试点 4：基数 0。测试 $0^b \bmod p$ 的稳定性。
4. 测试点 5-6：大质数与极端范围。$a, b, p$ 均接近 $2^{31}-1$，测试 long long 是否溢出。
5. 测试点 7-10：全随机大规模数据。利用 mt19937 生成高随机性的 $2^{31}$ 以内的整数。

数据生成器 C++ 代码

#include <iostream>
#include <fstream>
#include <string>
#include <random>
#include <ctime>

using namespace std;

// --- 标程：迭代式快速幂，用于生成 .out 文件 ---
long long solve_std(long long a, long long b, long long p) {
    if (p == 0) return 0; // 虽然题目说 p >= 1，但习惯性防御
    long long res = 1 % p;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// --- 辅助函数：将数据写入文件 ---
void write_test_case(int id, long long a, long long b, long long p) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    // 写入输入文件
    ofstream fout(in_name);
    fout << a << " " << b << " " << p << endl;
    fout.close();

    // 写入输出文件（按题目要求的格式）
    ofstream fans(out_name);
    long long ans = solve_std(a, b, p);
    fans << a << "^" << b << " mod " << p << "=" << ans << endl;
    fans.close();

    cout << "Generated case " << id << ": " << a << " " << b << " " << p << " -> ans: " << ans << endl;
}

int main() {
    // 使用 mt19937 获得高质量随机数
    mt19937_64 rng(time(0));
    const long long MAX_VAL = 2147483647LL; // 2^31 - 1

    // Case 1: 官方样例
    write_test_case(1, 2, 10, 9);

    // Case 2: 指数为 0 的情况 (a^0 mod p = 1 % p)
    write_test_case(2, 1234567, 0, 10007);

    // Case 3: 模数为 1 的情况 (结果必须为 0)
    write_test_case(3, 987654, 321, 1);

    // Case 4: 基数为 0 的情况
    write_test_case(4, 0, 100, 7);

    // Case 5: 极限范围 (全最大值)
    write_test_case(5, MAX_VAL, MAX_VAL, MAX_VAL);

    // Case 6: 2 的幂次 (测试位移累积)
    write_test_case(6, 2, 31, MAX_VAL);

    // Case 7-10: 全随机数据
    for (int i = 7; i <= 10; ++i) {
        long long a = rng() % (MAX_VAL + 1);
        long long b = rng() % (MAX_VAL + 1);
        long long p = (rng() % MAX_VAL) + 1; // 确保 p >= 1
        write_test_case(i, a, b, p);
    }

    cout << "\n所有 10 组测试数据已生成完成。" << endl;
    return 0;
}

数据生成器设计要点说明：

1. 文件大小优化：
   • 该题输入仅三个数字，输出为一个简短字符串。
   • 10 个测试点的总大小约为几百字节，远低于 2MB 限制，极大节省了 OJ 加载时间。
2. 安全性（除零与溢出）：
   • 在随机生成 p 时，使用了 + 1 确保模数不为 0。
   • 标程中使用 long long 承载 $a \times a$。因为 $a < 2^{31}$，所以 $a^2 < 4 \times 10^{18}$，而 long long 最大约为 $9 \times 10^{18}$，计算过程中恰好不会溢出。如果 $p$ 范围再大（如 $10^{18}$），则生成器内需要使用 __int128。
3. 区分度：
   • 通过构造 $b=0$ 和 $p=1$ 的数据，可以区分出代码中忽略了初始取模或递归边界处理不当的程序。
4. 非递归实现：
   • 数据生成器中的 solve_std 使用了迭代写法，确保在生成大规模数据的正确解时，不会因为递归深度导致生成器自身崩溃。

使用方法：

1. 将上述代码保存为 gen.cpp。
2. 使用 g++ gen.cpp -o gen -O2 编译。
3. 运行 ./gen，当前目录下会立即生成 1.in, 1.out ... 10.in, 10.out。
4. 将这些文件打包上传至你的 OJ 题目后台即可。

在 NOI 竞赛中，快速幂是数论板块最基础、最重要的工具。几乎所有涉及大数取模的题目（如组合数学、矩阵加速、逆元计算）都离不开它。

以下是从暴力模拟到最优倍增算法的演进过程。

---

版本一：暴力模拟算法 ($O(b)$)

思路分析： 最直观的想法是通过循环将 $a$ 连乘 $b$ 次。每乘一次就取一次模，防止溢出。

#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    long long a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;

    long long res = 1 % p; // 处理 p=1 的特殊情况
    long long base = a % p;

    // 循环 b 次，时间复杂度 O(b)
    for (int i = 1; i <= b; ++i) {
        res = (res * base) % p;
    }

    printf("%lld^%lld mod %lld=%lld\n", a, b, p, res);
    return 0;
}

• 时间复杂度：$O(b)$。当 $b=2^{31}-1$ 时，计算次数超过 21 亿次，在 1 秒时限内必然 TLE。
• 空间复杂度：$O(1)$。

---

版本二：递归式快速幂 ($O(\log b)$)

思路分析： 基于分治思想。计算 $a^b$ 可以转化为：

• 如果 $b$ 是偶数，$a^b = (a^{b/2})^2$。
• 如果 $b$ 是奇数，$a^b = a \times (a^{b/2})^2$。

#include <iostream>
#include <cstdio>

using namespace std;

// 递归实现分治
long long qpow_recursive(long long a, long long b, long long p) {
    if (b == 0) return 1 % p; // 递归边界：任何数的 0 次方是 1
    
    long long half = qpow_recursive(a, b / 2, p);
    
    // 中间结果必须存入 long long，否则 half * half 可能会溢出 int
    long long res = (half * half) % p;
    
    if (b % 2 == 1) { // 如果指数是奇数，补乘一个 a
        res = (res * (a % p)) % p;
    }
    return res;
}

int main() {
    long long a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) == 3) {
        printf("%lld^%lld mod %lld=%lld\n", a, b, p, qpow_recursive(a, b, p));
    }
    return 0;
}

• 时间复杂度：$O(\log b)$。每次递归 $b$ 减半，深度仅约 31 层。
• 空间复杂度：$O(\log b)$。主要是递归调用的系统栈开销。

---

版本三：迭代式快速幂（最优复杂度与常数）

思路分析： 利用二进制拆分指数 $b$。例如 $13$ 的二进制是 $1101$，即 $13 = 2^3 + 2^2 + 2^0$。 那么 $a^{13} = a^{2^3} \times a^{2^2} \times a^{2^0}$。 我们通过位运算 & 1 检查当前位是否需要累乘到答案中，并用 >> 1 移动到下一位。

#include <iostream>
#include <cstdio>

using namespace std;

/**
 * 竞赛标准快速幂模板
 * 易错点：
 * 1. a * a 可能会超过 long long 吗？本题 p < 2^31，a < 2^31，
 *    a * a 最大约为 4 * 10^18，long long（最大 9 * 10^18）勉强能装下。
 * 2. 初始 res 必须先模 p，处理 p=1 的情况。
 * 3. 输入 a 也要先模 p，防止 a 很大。
 */
long long fast_pow(long long a, long long b, long long p) {
    long long res = 1 % p; 
    a %= p; // 初始取模，保证 base 在 [0, p-1] 范围内
    
    while (b > 0) {
        // 如果当前二进制位为 1，则将当前的权重乘入结果
        if (b & 1) {
            res = (res * a) % p;
        }
        // base 自乘：a^1 -> a^2 -> a^4 -> a^8 ...
        a = (a * a) % p;
        // 指数右移，处理下一位
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, b, p;
    // 使用 scanf 以提高读入速度
    if (scanf("%lld %lld %lld", &a, &b, &p) == 3) {
        long long ans = fast_pow(a, b, p);
        // 按照题目要求的格式输出
        printf("%lld^%lld mod %lld=%lld\n", a, b, p, ans);
    }
    return 0;
}

---

时间复杂度分析思考过程

1. 分治的威力：

   • 在 $b = 2^{31}$ 时，线性 $O(b)$ 需要计算 $2,147,483,648$ 次。
   • 快速幂 $O(\log b)$ 只需要循环 $\approx 31$ 次。
   • 结论：快速幂实现了从“天文数字”级计算到“纳秒”级计算的飞跃。

2. 空间复杂度分析：

   • 迭代版本仅使用 3 个变量，空间复杂度为 $O(1)$，在内存受限的竞赛题目中表现更佳。

---

时间复杂度优化建议

1. 位运算优化：

   • 使用 b & 1 替代 b % 2 != 0。
   • 使用 b >>= 1 替代 b /= 2。
   • 这些操作在现代编译器下虽有自动优化，但手动书写体现了竞赛选手的专业素质。

2. 溢出预防（NOI 进阶）：

   • 如果题目要求 $p$ 的范围达到 $10^{18}$（超过 long long 的平方），a * a % p 会直接溢出。
   • 对策：需要使用“快速乘”（利用 __int128 或类似的倍增乘法）来替代普通的乘法取模。

3. 读题关键词总结：

   • “结果对 M 取模”：必须全程取模。
   • “指数很大”：必须使用快速幂。
   • “a, b < 2^31”：意味着乘法会超过 int，必须用 long long。

NOI 竞赛模拟题：P1226 【模板】快速幂

题目描述

给你三个整数 $a, b, p$，求 $a^b \bmod p$。

在 NOI 竞赛中，这是处理大数幂次模运算的必备工具。你需要实现一个时间复杂度为 $O(\log b)$ 的算法来解决此问题，以应对大规模数据的挑战。

---

输入格式

输入只有一行，包含三个整数 $a, b, p$。

输出格式

输出一行一个字符串，格式为 a^b mod p=s，其中 $s$ 为计算结果。

---

输入输出样例

样例 1

输入：

2 10 9

输出：

2^10 mod 9=7

---

数据范围与提示

• 对于 $100\%$ 的数据，$0 \le a, b < 2^{31}$，$1 \le p < 2^{31}$。
• 注意：$b=0$ 时的特殊处理，以及乘法过程中可能产生的整数溢出。

---

1. 预备知识点

• 倍增思想（Binary Lifting/Exponentiation）：将指数 $b$ 进行二进制拆分。
• 同余模运算性质：$(a \times b) \bmod p = ((a \bmod p) \times (b \bmod p)) \bmod p$。
• 位运算：使用 & 1 判断奇偶，使用 >> 1 进行减半处理。
• 数据类型：由于 $a, p$ 可达 $2 \times 10^9$，中间乘法结果会超过 int 范围，必须使用 long long。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：朴素算法的局限性

我们要计算 $2^{10} \bmod 9$。 如果连乘 10 次：$2 \times 2 \times 2 \dots \times 2$，时间复杂度是 $O(b)$。当 $b = 2^{31}-1$ 时，计算量约 21 亿次，在 1 秒时限内必 TLE。

第二步：倍增思想的介入

观察指数 $10$ 的二进制：$10 = (1010)_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$。 所以：$a^{10} = a^{2^3} \times a^{2^1}$。

我们只需要维护一个变量 base，让它不断自乘：

1. base 初始为 $a^1$。
2. base 自乘变为 $a^2$。
3. base 再自乘变为 $a^4$。
4. base 再自乘变为 $a^8$。

第三步：如何在代码中实现

我们在纸上模拟 $a=2, b=10, p=9$：

• 初始化：ans = 1, base = 2 % 9 = 2, b = 10。
• 第一轮：$10$ 是偶数（最低位为 0）。base 自乘：base = 2 * 2 = 4, b 变为 $5$。
• 第二轮：$5$ 是奇数（最低位为 1）。ans = ans * base = 1 * 4 = 4。base 自乘：base = 4 * 4 = 16 % 9 = 7, b 变为 $2$。
• 第三轮：$2$ 是偶数。base 自乘：base = 7 * 7 = 49 % 9 = 4, b 变为 $1$。
• 第四轮：$1$ 是奇数。ans = ans * base = 4 * 4 = 16 % 9 = 7。b 变为 $0$。
• 结束：输出 7。

第四步：复杂度与溢出思考

• 时间复杂度：指数 $b$ 每次减半，总循环次数为 $\log_2 b$，约为 31 次。
• 溢出预防：ans * base 可能达到 $10^{18}$ 级别，必须使用 (long long)ans * base % p。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 读入 a, b, p"] --> B["初始化 ans 等于 1 模 p"]
    B --> C["更新 a 等于 a 模 p"]
    C --> D{"b 是否大于 0?"}
    D -- "否" --> E["输出格式化结果 ans"]
    D -- "是" --> F{"b 的最低位是否为 1?"}
    F -- "是" --> G["更新 ans 等于 ans 乘以 a 再模 p"]
    F -- "否" --> H["更新 a 等于 a 乘以 a 再模 p"]
    G --> H
    H --> I["更新 b 等于 b 右移一位"]
    I --> D

---

4. 读题关键词与优化建议

读题关键词

1. “模 p”：所有涉及乘法的地方都必须加上 % p。
2. “2^31”：提示必须使用 long long 承载中间计算。
3. “a^b”：当 $b=0$ 且 $p=1$ 时，结果应为 $1 \bmod 1 = 0$。

复杂度分析过程

• 时间复杂度：$O(\log b)$。每次循环指数规模减小一半。
• 空间复杂度：$O(1)$。仅需常数个变量存储。

优化建议

• 位运算替代：使用 b & 1 替代 b % 2 == 1；使用 b >>= 1 替代 b /= 2。在 NOI 评测中，这能带来微小的常数优化。
• 初始取模：如果 $a > p$，初始化时应先 a %= p，防止第一次自乘就溢出。
• 特殊情况：处理 $p=1$ 的情况，此时任何数模 1 均为 0。

---

5. 总结：此类题型的关键词

在阅读 NOI 题目时，看到以下关键词应立即联想到快速幂：

• “求幂” 或 “次方”。
• “结果对 M 取模”。
• “指数很大”（如 $10^9$ 或 $10^{18}$）。
• “组合数取模” 或 “矩阵加速”（矩阵快速幂的基础）。