题目描述

给定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

算法

快速幂

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

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

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        printf("%d\n",qmi(a,b,p));
    }
    return 0;
}