给定n组ai,bi,pi,对于每组数据,求出abii mod pi的值。
输入格式
第一行包含整数n。
接下来n行,每行包含三个整数ai,bi,pi。
输出格式
对于每组数据,输出一个结果,表示abii mod pi的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2∗109
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll oo(ll n,ll k,ll p)
{
ll res=1;
while(k)
{
if(k&1)res=res*n%p; //如果二进制数最后一位为 1 相乘;
k>>=1; //幂数左移;
n=n*n%p; //更新n
}
return res;
}
int main()
{
ll k;
cin>>k;
while (k--)
{
ll n,k,p;
cin>>n>>k>>p;
cout<<oo(n,k,p)<<endl;
}
}