Modular Exonentiation

#1

according to
(a^2)%b=(aa)%b=((a%b)(a%b))%b=((a%b)^2)%b OR
(a^b)%c=((a%c)^b)%c, I have written a code https://ide.codingblocks.com/s/208033 , but it is showing half of the test cases wrong.

#2

hey @AlphaX there are couple of mistakes in your code

  1. you also need to take modulo inside the function modulo exponentiation
  2. you need to use long long as int is not enough.

Rectified code:

#3

i had made all variables as long long but getting wrong ans when not taking modulo inside the function. So, why we have to take modulo inside the function? why can’t we get ans with my above concept?

#4

Because say a = 10, b = 100, c = 100 if you wont take modulo inside function you’ll be essentially calculating 10^100 inside your function. Is it possible to store number this big inside int or long long int.?