found this problem in a book to compute a ^ b ^ c mod p where p is prime and a, b, c are long longs.

what can be the best way??

found this problem in a book to compute a ^ b ^ c mod p where p is prime and a, b, c are long longs.

what can be the best way??

7 Likes

Compute res=(b^c) mod (p-1) using fast exponentiation method and then (a^res)mod p using the same.

5 Likes

Hello , the answer that @phantom11 gave is based on Fermatâ€™s Little theorem .

Fermatâ€™s Little theorem states that a^(p-1) = 1 (mod p) . Where p is prime . This is valid for all integers a .

So if you have to calculate a^b mod ( p ) and b = k * (p-1) + m . Then you know a^b = (a^(p-1))^k * a^m . = 1^k * a^m = a^m . So yes you can indeed extend this to optimize calculation of a^b . And also you can use above to calculate a1^a2^a3â€¦ modulo a prime number p.

13 Likes

@code_master01 : Yes if a is divisible by p , answer will be 0 . I thought you will take a mod p in the beginning itself and if its zero you output 0.

Also it doesnâ€™t seem to extend easily as you said .

1 Like

this is also related to a cool spoj problemâ€¦

can u explain how would this work exactlyâ€¦??

also, can i extend your answer to the possibility of optimizing

the calculation of a ^ b % m by doing b %= (m-1) beforehandâ€¦??

is there any exceptional/corner case??

thanx for the nice explanationâ€¦

However, the wikipedia page for â€śfermatâ€™sâ€ť little theorem states that the relation a^(p-1) = 1 (mod p) would hold only in the case when a is not divisible by prime p. I guess in our case this should not affect anything 'coz if a % p == 0 then answer will automatically be zero.

Also, when we extend this for a1^a2^a3â€¦ modulo a prime number p

i shud calculate a2 ^ a3 mod (p-1) but a3 ^ a4 modulo (what)??(considering that p - 1 will not be prime)

@surajtripathi : I will answer that . You question seems related to an ongoing contest at hackerrank , so I will answer it only after the contest is over which is five hours from now . I have solved all questions in Ad Infinitum at Hackerrank , you are welcome to ask your questions after the contest is over .