拓展: 如果 $k$ 可以为负数, 即 $a^{-|k|}$ (这样写是为了方便看(因为严格来讲k现在是负数)) 那么可以先求 $a^{|k|}$ 然后 返回 $1/a^{|k|}$ (注: 返回值为double), 特判 k 为负数的情况. (可以试试力扣pow(x, y)这题)❤️

#include <iostream>
using namespace std;

using ll = long long;

ll myPow(ll a, ll k, ll p) {
	ll res = 1;
	while (k) {
		if (k & 1)
			res = res * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		ll a, k, p;
		cin >> a >> k >> p;
		cout << myPow(a, k, p) << '\n';
	}
	return 0;
}