信奥赛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;}功能分析
快速幂算法原理：
- 二进制分解思想：将指数b用二进制表示，通过不断平方和相乘来计算结果
- 时间复杂度：O(log b)，远优于朴素的O(b)方法
- 空间复杂度：O(1)
算法步骤：
- 初始化结果ans = 1
- 当指数b > 0时循环：
- 如果b是奇数（b & 1 == 1），将当前底数a乘到结果ans中
- 将底数a平方（a = a * a）
- 将指数b右移一位（b = b / 2）
- 返回最终结果
取模运算的重要性：
- 防止数值溢出
- 满足题目要求的模运算
快速幂算法与倍增算法的关系
快速幂算法本质上是倍增算法思想在幂运算上的具体应用。
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;}
