数学知识：快速幂—快速幂

题目：AcWing 875. 快速幂
给定 n 组 a_i,b_i,p_i，对于每组数据，求出 a_i^bimod p_i 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含三个整数 a_i,b_i,p_i。

输出格式
对于每组数据，输出一个结果，表示 a_i^bimod p_i 的值。

每个结果占一行。

数据范围
1≤n≤100000,
1≤a_i,b_i,p_i≤2×10⁹

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

题目分析：
求 a_i^bimod p_i
先预处理出：
a的2⁰次方 mod p
a的2¹次方 mod p
…
a的2^logk次方 mod p
然后将bi次方转化为x2⁰+x2¹+…x2^logk
这是运用二进制的性质

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long LL;

LL qmi(int a,int k,int p)
{
    
    LL res=1%p;
    while(k)
    {
    
        if(k&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int main()
{
    
    int n;
    scanf("%d",&n);
    
    while(n--)
    {
    
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}