AcWing 875. 快速幂
给定nn组ai,bi,piai,bi,pi，对于每组数据，求出abii mod piaibi mod pi的值。

输入格式

第一行包含整数nn。

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

输出格式

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

每个结果占一行。

数据范围

1≤n≤1000001≤n≤100000,
1≤ai,bi,pi≤2∗1091≤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 qmi(int a,int b,int p)// Eg:b是a的k次方的中的k的二进制表示  (k = (10110)2)  a^k = a^2^0+a^2^1+a^2^2+...a^2^n
{
    LL res = 1%p;
    while(b){
        if(b&1)//如果b的二进制数最后一位是1
            res = res*a%p;//就是a的2的零次方*1
        a = a*(LL)a%p;//把a的2的零次方变为a的2的1次方，依此递增，
        b >>=1;//将b的最后一位数去掉
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        printf("%lld\n",qmi(a,b,p));

    }
    return 0;
}