版权声明:本文为博主原创文章,遵循 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
整数快速幂的时间复杂度是
,可以防止TLE,有非递归和递归俩种算法,我是看晴神的《算法笔记》上理解的。
#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;
}