Binary exponentiation
Fri Jan 21 2022 11:52:15 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
//time complexity:- O(log p)
ll bpow(ll b, ll p, ll m)
{
// power is 0 or base is 1 return 1
if (p == 0 || b == 1)
return 1;
// if power is odd
if (p & 1)
{
p >>= 1; // divide power by 2
ll t = bpow(b, p, m);
t = (1ll * t * t % m);
return (1ll * b * t % m);
}
// if power is even
else
{
p >>= 1;
ll t = bpow(b, p, m);
return (1ll * t * t % m);
}
}
content_copyCOPY
Comments