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??
5 Likes
Compute res=(b^c) mod (p-1) using fast exponentiation method and then (a^res)mod p using the same.
4 Likes
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??
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.
12 Likes
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)
@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
@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 .
this is also related to a cool spoj problem…