快速幂（欧拉降幂C++）

给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

C++

#include
#include

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1)res = (LL)res * a % p;
		k >>= 1;
		a = (LL)a * a % p;
	}
	return res;
}

int main()
{
	int n;
	scanf_s("%d", &n);
	while (n--)
	{
		int a, k, p;
		scanf_s("%d%d%d", &a, &k, &p);

		printf("%dn", qmi(a, k, p));
	}
	return 0;
}