You are viewing a single comment's thread. Return to all comments →

So, in our next step we need the help of higher powers, or we need to calculate ab %m.

= 1 % m , b == 0 a^b = a*(a^(b-1)) % m , odd b = a'^2 % m , even b where a' = a^(b/2)

Suppose we need to calculate 2100 % 11.

2^100 = (2^50)^2 (mod 11) 2^50 = (2^25)^2 (mod 11) 2^25 = 2*(2^24) (mod 11) 2^24 = (2^12)^2 (mod 11) 2^12 = (2^6)^2 (mod 11) 2^6 = (2^3)^2 (mod 11) 2^3 = 2*(2^2) (mod 11) 2^2 = (2^1)^2 (mod 11) 2^1 = 2*(2^0) (mod 11) 2^0 = 1

Now popping whole stack,

2^1 = 2*1 = 2 (mod 11) 2^2 = 2^2 = 4 (mod 11) 2^3 = 2*4 = 8 (mod 11) 2^6 = 8^2 = 64 = 9 (mod 11) 2^12 = 9^2 = 81 = 4 (mod 11) 2^24 = 4^2 = 16 = 5 (mod 11) 2^25 = 2*5 = 10 (mod 11) 2^50 = 10^2 = 100 = 1 (mod 11) 2^100 = 1^2 = 1 (mod 11)

thank you very much,it works!

Sir please check my program , I am getting wrong answer . I have implemented your concept https://www.hackerrank.com/challenges/sherlock-and-permutations/submissions/code/18386949

## Sherlock and Permutations

You are viewing a single comment's thread. Return to all comments →

So, in our next step we need the help of

higher powers, or we need to calculateab %m.Suppose we need to calculate

2100 % 11.Now popping whole stack,

thank you very much,it works!

Sir please check my program , I am getting wrong answer . I have implemented your concept https://www.hackerrank.com/challenges/sherlock-and-permutations/submissions/code/18386949