题解：P1226 【模板】快速幂

· · 题解

简练概述

给你很大的数 a, b, p，让你计算 a^b \bmod p。

这是一道很好的模版题，解决方法有很多，用余数的性质甚至还可以达到常数级别，~虽然我忘了吧~。

快速幂算法详解

算法介绍

快速幂算法是一种用于高效计算大整数幂模运算的算法。其核心思想是通过将指数 b 分解为二进制形式，利用幂的平方性质将计算复杂度从 O(b) 降低到 O(\log b)。

快速幂的核心思想

  1. 幂的平方性质：对于任意整数 a 和 b，有 a^b = (a^{b/2})^2（当 b 为偶数时）或 a^b = a \times (a^{(b-1)/2})^2（当 b 为奇数时）。
  2. 二进制分解：将指数 b 表示为二进制形式，例如 b = 2^{k_1} + 2^{k_2} + \dots + 2^{k_n}，然后通过迭代计算 a^{2^k} 来快速得到结果。

算法步骤

  1. 初始化结果为 1。
  2. 将指数 b 转换为二进制形式。
  3. 遍历 b 的二进制位：
    • 如果当前位为 1，则将结果乘以 a 的当前幂次。
    • 将 a 平方，继续处理下一位。
  4. 最终结果即为 a^b \bmod p。

正确性证明

快速幂算法的正确性基于以下数学性质：

  1. 幂的平方性质：对于任意整数 a 和 b，有： a^b = \begin{cases} (a^{b/2})^2 & \text{如果 } b \text{ 是偶数}, \\ a \times (a^{(b-1)/2})^2 & \text{如果 } b \text{ 是奇数}. \end{cases}
  2. 模运算的分配律：对于任意整数 a, b, p，有： (a \times b) \bmod p = [(a \bmod p) \times (b \bmod p)] \bmod p.

通过将指数 b 分解为二进制形式，快速幂算法能够将计算 a^b \bmod p 的复杂度从 O(b) 降低到 O(\log b)，同时保证结果的正确性。

代码实现

以下是快速幂算法的 C++ 实现代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a, b, p, s;
// 快速幂函数
int ksm(int a, int b, int p) {
    int sum = 1; // 初始化结果为 1
    a = a % p; // 先对 a 取模，防止溢出
    while (b > 0) {
        // 如果当前二进制位为 1，将结果乘以 a
        if (b & 1) {
            sum = (sum * a) % p;
        }
        // 将 a 平方，继续处理下一位
        a = (a * a) % p;
        b = b >> 1; // 右移一位，相当于 b /= 2
    }
    return sum;
}
signed main() {
    cin >> a >> b >> p;
    s = ksm(a, b, p);
    cout << a << "^" << b << " mod " << p << "=" << s;
    return 0;
}