[number theory] fast power (Euler power)

subject

explain

• 

• O(n∗logb) 

Code segment

#include<iostream>
#define ll long long
using namespace std;
ll qmi(ll a,ll k,ll p)
{
    ll res=1;
    while(k)// Yes b Binarization , From low to high 
    {
// If b The binary representation of 0 Position as 1, Then multiply by the current a
        if(k&1)res=res*a%p;
//b Moves to the right one 
        k>>=1;
// to update a,a In turn a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
        a=a*a%p;
    }
    return res;
}
int main()
{
    int n;cin>>n;
    while(n--)
    {
    
    ll a,k,p;
    cin>>a>>k>>p;
    cout<<qmi(a,k,p)<<endl;
    }
    
}