题解 | #快速幂#
快速幂
https://www.nowcoder.com/practice/defdedf4fe984c6c91eefa6b00d5f4f0
#include <iostream>
using namespace std;
typedef long long ll;
//快速幂FastPower
ll fp(ll a, ll b, ll c)
{
ll ans = 1;
while (b)
{
if (b & 1)//如果b是奇数，二进制末位是1
{
ans*= a;
}
ans %= c;//取模防止超范围
a = ((a%c)*(a%c))%c;
b>>=1;//右移一位
}
return ans%c;
}
int main() {
ll a, b, q, p;
cin >> q;
while (q--)
{
cin >> a >> b >> p;
cout << fp(a, b, p)<<endl;
}
return 0;
}
关于快速幂的介绍可以看这个视频：https://www.bilibili.com/video/BV12r4y1w7tx?spm_id_from=333.337.search-card.all.click
