题解 | #【模板】快速幂#

#include<bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long b,long long mod)
{
	long long ans=1;//后续要对其进行乘法操作，所以不可以设成0；
	a%=mod;//防止a过大，直接对其取模
	while(b)//当指数b不为0时；
	{
		if(b&1)//b%2==1指数b为奇数；或者使用b&1，&：在二进制下b为奇数
		{
			ans=(ans*a)%mod;//先将ans乘以a；
			a=(a*a)%mod;//再将底数平方；
			b>>=1;//再将指数除以2；最后1/2==0；输出ans
			
		}
		else//指数b为偶数时，只需要将指数b除以2，底数平方；
		{
			b>>=1;//在二进制中相当于b/=2;运算速度更快,当最后b==2时，b/=2等于1；再次执行一次上面的if
			a=(a*a)%mod;
		}
	}
	return ans;
	
}


int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//这段代码的主要用途是在C++中关闭输入输出流的同步，以提高程序的执行效率。
	int t;long a,b,mod;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>mod;
		cout<<qpow(a,b,mod);
	}
	
}