原理

在指数b大于0时:

若b为奇数,先将ans单独乘以底数a并mod m, 再将底数平方并mod m
若b为偶数,将底数平方并mod m

b右移一位,即b/2
时间复杂度:O(lognlogn)
数学理解很简单,位运算参考这个

模版

#include<cstdio>
using namespace std;
typedef long long ll;
ll qpower(ll, ll, ll);
int main()
{
	ll a, b, m;
	scanf("%lld%lld%lld", &a, &b, &m);
	printf("%lld", qpower(a, b, m));
 } 
ll qpower(ll a, ll b, ll m)
{
	ll ans = 1, res = a;
	while(b > 0)
	{
		if(b & 1)
			ans = ans*res%m;
		res = res*res%m;
		b >>= 1;
	}
	return ans;
}