题目描述

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

using namespace std;
typedef long long LL;

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL) res * a % p;//两数相乘可能会爆Int
        k >>= 1;//移去最低位
        a = (LL) a * a % p;// 计算后, a平方
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }

    return 0;
}