O(logB) solution with recursion


#1

#define ll long long

ll power(ll a,ll b,ll c)
{
if(b==0)
return 1;
if(b==1)
return a%c;
ll res = power(a,b/2,c)%c;
if(b%2==0)
return (res * res)%c;
return ((res * res)%c * (a%c))%c;
}

int Solution::Mod(int A, int B, int C)
{
if(A==0)
return 0;
if(A<0)
A = (A%C + C)%C;
return power(A,B,C);
}