how to solve this Problem. since n can be of the order 10^18, can it really be solved using just memoization(i don't think so) ? can this problem be solved using matrix exponentiation, but the recurrence is not linear. Help. I came up with THIS CODE, can anyone point out why it is giving wrong answer ? asked 24 Oct '16, 17:14

You dont actually need to take log on values. It was for explanation purpose. Using the property: a^(log b(base a) ) = b, you can avoid log and double and smoothly work with long integers. answered 24 Oct '16, 19:14
hey!! i understood what you said. here is my solution http://ideone.com/m19TN6 Its not very long :). but it is giving wrong answer, i don't know why. can you tell me whats wrong with it ?
(24 Oct '16, 20:49)
in matrix multiplication, replace %mod by %(mod1) and get AC!
(24 Oct '16, 21:16)
and the reason is ? stil not getting AC http://ideone.com/sPPc4a, care to try ?
(24 Oct '16, 21:19)
link not working!
(24 Oct '16, 23:19)
try this http://ideone.com/sQfhNa , can you please explain the reason meanwhile. I can see that you mean, we have to take the mod to be equal to its euler totient number during matrix exponentiation, but i don't see the WHY behind it. :\
(24 Oct '16, 23:44)
You are right. This is because you will raise them to power of integers, and its direct result of Fermat's Theorem. Also, use long for n.
(25 Oct '16, 09:18)
i know about Fermat theorem it says a^phi(n) is = 1 mod(n) so if we are given, a^k mod(n), we can reduce it to a^(k mod( phi(n) ) ) mod(n). right ? we still have to take the number mudulo n(and not phi(n)) after exponentiation right ? so first. it reduces the exponent which seems to be an optimization as we are already doing binary exponentiation. second, does this hold for matrix as well, as we know the equation holds only if a belongs to multiplicative modulo group of n, that is, if they are coprime, so how can we say a matrix is coprime to a number ? links are welcome too. :)
(25 Oct '16, 15:37)
i dont know whether they hold for matrices!
(25 Oct '16, 18:08)
showing 5 of 8
show all
