Mathematical knowledge: fast power fast power

subject ：AcWing 875. Fast power
Given n Group a_i,b_i,p_i, For each set of data , Find out a_i^bimod p_i Value .

Input format
The first line contains integers n.

Next n That's ok , Each line contains three integers a_i,b_i,p_i.

Output format
For each set of data , Output a result , Express a_i^bimod p_i Value .

Each result takes up one line .

Data range
1≤n≤100000,
1≤a_i,b_i,p_i≤2×10⁹

sample input ：

2
3 2 5
4 3 9

sample output ：

4
1

Topic analysis ：
seek a_i^bimod p_i
Preprocess first ：
a Of 2⁰ Power mod p
a Of 2¹ Power mod p
…
a Of 2^logk Power mod p
And then bi Power conversion to x2⁰+x2¹+…x2^logk
This is the use of binary properties

#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;
}