题目内容

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

输入格式

第一行包含整数n。

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

输出格式

对于每组数据，输出一个结果，表示ai^bi mod pi的值。

每个结果占一行

数据范围

1≤n≤100000 ,
1≤ai,bi,pi≤2*10^9

输入样例

2
3 2 5
4 3 9

输出样例

4
1

题解

快速幂解释

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

//a^k % p
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1; //把k的末位删掉
        a = (LL)a*a % p;
    }
    return res;
}

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