简练概述

快速幂算法详解

算法介绍

快速幂的核心思想

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.$$

代码实现

#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;
}