【蓝桥杯】ADV-204 快速幂
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/102989593
题目描述：
给定A, B, P，求(A^B) mod P。
输入描述：
输⼊共⼀⾏。 第⼀⾏有三个数，N, M, P。（A, B为long long范围内的⾮负整数，P为int内的⾮负整数）。
输出描述：
一个整数，表示箱子剩余空间。
输入样例：
2 5 3
输出样例：
2
解题思路：
整数快速幂的时间复杂度是
{\color{Green} O(log_{2}n)}
，可以防止TLE，有非递归和递归俩种算法，我是看晴神的《算法笔记》上理解的。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickPow(ll x,ll n,ll m) //整数快速幂,计算x^n%m
{
ll ans = 1;
x %= m;
while(n)
{
if(n&1) //奇数
{
ans = ans*x%m;
}
x = x*x%m;
n >>= 1;
}
return ans;
}
ll binaryPow(ll x,ll n,ll m) //整数快速幂,计算x^n%m递归求解
{
if(n == 0) return 1; //若n为0,则x^0=1
else if(n&2) //若n为奇数,转换为n-1
{
return n*binaryPow(x,n-1,m)%m;
}
else //若n为偶数,转换为n/2
{
ll ans = binaryPow(x,n/2,m);
return ans*ans%m;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
ll a,b,m;
cin >> a >> b >> m;
cout << quickPow(a,b,m) << endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录