信奥赛C++提高组csp-s之快速幂

信奥赛C++提高组csp-s之快速幂

题目描述

给你三个整数a , b , p a,b,pa,b,p，求a b m o d p a^b \bmod pabmodp。

输入格式

输入只有一行三个整数，分别代表a , b , p a,b,pa,b,p。

输出格式

输出一行一个字符串a^b mod p=s，其中a , b , p a,b,pa,b,p分别为题目给定的值，s ss为运算结果。

输入输出样例 1

输入 1

2 10 9

输出 1

2^10 mod 9=7

说明/提示

样例解释

2 10 = 1024 2^{10} = 1024210=1024，1024 m o d 9 = 7 1024 \bmod 9 = 71024mod9=7。

数据规模与约定

对于100 % 100\%100%的数据，保证0 ≤ a , b < 2 31 0\le a,b < 2^{31}0≤a,b<231，a + b > 0 a+b>0a+b>0，2 ≤ p < 2 31 2 \leq p \lt 2^{31}2≤p<231。

AC代码1（迭代实现）

#include<bits/stdc++.h>usingnamespacestd;longlonga,b,p;// 快速幂取模函数longlongqpow(longlonga,longlongb){longlongans=1;// 初始化结果为1// 当指数b不为0时循环while(b){// 如果b的二进制最低位为1（即b为奇数）if(b&1){ans=ans*a%p;// 将当前的a乘到结果中，并取模ans%=p;// 再次取模确保结果正确（实际上前一步已经取模，这步是冗余的）}a=a*a%p;// 将底数平方，并取模b>>=1;// 将指数右移一位（相当于除以2）}returnans;// 返回最终结果}intmain(){// 读取输入：底数a，指数b，模数pcin>>a>>b>>p;// 输出结果，格式为：a^b mod p=计算结果cout<<a<<"^"<<b<<" mod "<<p<<"="<<qpow(a,b);return0;}

功能分析

快速幂算法原理：

1. 二进制分解思想：将指数b用二进制表示，通过不断平方和相乘来计算结果
2. 时间复杂度：O(log b)，远优于朴素的O(b)方法
3. 空间复杂度：O(1)

算法步骤：

1. 初始化结果ans = 1
2. 当指数b > 0时循环：
   • 如果b是奇数（b & 1 == 1），将当前底数a乘到结果ans中
   • 将底数a平方（a = a * a）
   • 将指数b右移一位（b = b / 2）
3. 返回最终结果

取模运算的重要性：

• 防止数值溢出
• 满足题目要求的模运算

快速幂算法与倍增算法的关系

快速幂算法本质上是倍增算法思想在幂运算上的具体应用。

1. 倍增算法思想

倍增算法的核心思想是：通过已知的小规模结果，通过"翻倍"的方式快速得到大规模结果，从而将线性复杂度优化到对数复杂度。

基本模式：

• 从基础情况开始
• 每次将规模扩大一倍
• 通过组合小规模结果得到大规模结果

2. 快速幂作为倍增的应用

迭代快速幂的倍增过程：

// 倍增过程：a, a^2, a^4, a^8, a^16, ...while(b){if(b&1)ans=ans*a%p;// 组合阶段a=a*a%p;// 倍增阶段：当前值平方b>>=1;// 规模减半}

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}