我们在通常处理a^b问题中，一般来说第一时间想到的就是通过循环来暴力解决，但是这样的话时间复杂度就是o（n）。c++代码一秒的算力大概是1e7–1e8之间，倘若数据较大，题目就会超时导致TLE。因此，我们在这里介绍一下快速幂的算法。

题目引入AcWing a^b

求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数，表示a^b mod p的值。

数据范围
0≤a,b≤1e9
1≤p≤1e9

在这里，显然用暴力100%会导致超时，因此我们来看看快速幂。

快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
让我们先来看一个简单的例子：
3¹⁰=3*3*3*3*3*3*3*3*3*3
3¹⁰=(3*3)(3*3)(3*3)(3*3)(3*3)
3¹⁰=(3*3)⁵
3¹⁰=(3*3)⁵
9⁵=（9⁴）*（9¹）
9⁵=（9⁴）*（9¹）
9⁵=（6561¹）*(9¹)
以下以求a的b次方来介绍
把b转换成二进制数。
该二进制数第i位的权为2的i-1次方

例如a^11
11的二进制是1011
11=(2³)*1 + (2²)*0 + (2¹)*1 + (2⁰)*1
因此，我们将a¹¹转化为算a^{(2^0)}*a^{(2^1)}*a^{(2^3)}

代码实现

#include<iostream>
using namespace std;

int qmi(int m, int k, int p)//求m的k次方取余于p
{
	int res = 1%p, t = m%p;
	while (k)
	{
		if (k & 1)//{等效于if(k%2==1)}判断k转化为2进制后最后一位数是不是1
		{
			res = res * t % p;
		}
		t = t * t % p;
		k >>=1;//2进制数/2,即2进制删除最后一位数{等效于k/=2}
	}
	return res;
}

int main()
{
	int m, k, p;
	cin >> m >> k >> p;
	cout << qmi(m, k, p);
	return 0;
}

输入样例

3 2 7

输出样例

2