专栏文章

P1226 【模板】快速幂

FFishlinsihan
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioy5gqt
此快照首次捕获于
2025/12/03 03:04
3 个月前
此快照最后确认于
2025/12/03 03:04
3 个月前
查看原文
这段代码实现了快速幂算法，用于高效计算 ( B^P \mod K ) 的值。快速幂算法通过二分思想将指数分解，显著降低计算复杂度（从 ( O(P) ) 优化到 ( O(\log P) )。以下是对代码的详细解释：

代码功能

  1. 输入：三个整数 ( B )（底数），( P )（指数），( K )（模数）。
  2. 输出：格式化字符串 ( B^P \mod K = \text{result} )，其中 result 是计算结果。
  3. 核心算法：递归实现的快速幂，核心思想是：
    • ( a^b = \begin{cases} (a^{b/2})^2 & \text{if } b \text{ is even} \ (a^{b/2})^2 \times a & \text{if } b \text{ is odd} \end{cases} )

代码逐段分析

CPP
#include<cstdio>
long long B, P, K;  // 全局变量：底数B、指数P、模数K

// 快速幂递归函数
long long qpow(int base, int p) {
    if (p == 1) {          // 递归终止条件1：指数为1
        return base;       // 直接返回底数
    } else if (p == 0) {   // 递归终止条件2：指数为0
        return 1;          // 返回1（任何数的0次幂为1）
    } else {
        long long ans = qpow(base, p / 2) % K;  // 递归计算 base^(p/2)
        long long ans1 = (ans % K * ans % K) % K; // 平方结果并取模
        if (p % 2 == 1) {  // 若指数为奇数
            ans1 = (ans1 % K * base % K) % K; // 额外乘一次底数
        }
        ans1 = ans1 % K;   // 确保结果在[0, K-1]范围内
        return ans1;
    }
} 

int main() {
    scanf("%lld%lld%lld", &B, &P, &K);  // 输入B, P, K
    long long ans = qpow(B, P);         // 调用快速幂函数
    ans = ans % K;                      // 对结果再次取模（冗余但安全）
    printf("%lld^%lld mod %lld=%lld", B, P, K, ans); // 格式化输出
    return 0;
}

关键点说明

  1. 递归过程：
    • 分解：将 ( P ) 不断二分（p / 2），直到指数为0或1。
    • 合并：
      • 偶数时：( \text{ans1} = (\text{ans} \times \text{ans}) \mod K )
      • 奇数时：额外乘 ( B \mod K )。
  2. 模运算优化：
    • 每一步乘法后立即取模（% K），防止数值溢出并加速计算。
    • 最终结果再次取模确保正确性（尽管递归中已处理，这是冗余的安全措施）。
  3. 边界处理：
    • ( P = 0 )：返回1（数学定义）。
    • ( P = 1 )：直接返回 ( B )（未取模，依赖后续操作处理）。

存在的缺陷及修复建议

  1. 类型不匹配：
    • qpow 参数为 int，但输入 ( B, P ) 是 long long，大数会截断。
    • 修复：将函数签名改为 long long qpow(long long base, long long p)。
  2. 未处理 ( B \geq K ) 的情况：
    • 递归中直接使用 base 可能导致乘法溢出（如 base * base）。
    • 修复：进入递归前先取模 base %= K;。
  3. 递归深度问题：
    • ( P ) 较大时（如 ( 2^{31} )）递归约31层，可能栈溢出（尽管概率低）。
    • 优化：改用迭代版快速幂（见下方改进代码）。

改进代码（迭代版快速幂）

CPP
#include<cstdio>
using namespace std;

int main() {
    long long B, P, K;
    scanf("%lld%lld%lld", &B, &P, &K);
    long long base = B % K;  // 初始取模确保base < K
    long long exp = P;
    long long result = 1 % K; // 处理K=1的情况（但题目保证K≥2）

    while (exp > 0) {
        if (exp & 1) {               // 当前二进制位为1
            result = (result * base) % K; // 累积结果
        }
        base = (base * base) % K;    // 底数平方
        exp >>= 1;                   // 右移一位（指数除2）
    }

    printf("%lld^%lld mod %lld=%lld", B, P, K, result);
    return 0;
}

改进点

  1. 迭代代替递归：
    • 避免栈溢出风险。
    • 效率更高（无函数调用开销）。
  2. 二进制分解：
    • 通过 exp & 1 判断奇偶性。
    • 通过 exp >>= 1 右移实现指数二分。
  3. 鲁棒性：
    • 初始 base %= K 防止溢出。
    • 初始化 result = 1 % K 处理 ( P=0 ) 的情况。
此算法时间复杂度 ( O(\log P) )，完美支持题目数据范围（( 0 \leq B, P < 2^{31} )）。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...