The language for above problem is Vietnamese, do you want to get the link?

Use logarithmic exponentiation

Here is the c++ implimentation

int power(int a,int b){

long long x=1;

while(b){

if(b&1){

x*=a;

x%=mod;

}

a*=a;

a%=mod;

b>>=1;

}

return x;

}

I don’t know the question requiring, just understand that: "calculate a^b % c "

if a p = 0, then a^n p will always be zero.

1 Like

Oh :D, thank you

Don’t you think your if-else ladder for even exponent is very inefficient ?

Hi, just check 《Introduction to Algorithms, 3rd Edition》Chapter 31.6. Especially “Raising to powers with repeated squaring” section

In order to calculate a^b(mod n):

```
MODULAR-EXPONENTIATION(a, b, n)
c = 0
d =1
let <bk,bk-1,...,b0> be the binary representation of b
for i = k downto 0
c = 2c
d = (d * d) mod n
if (bi == 1)
c = c + 1
d = (d * a) mod n
return d
```