You are not logged in. Please login at to post your questions!



how to solve this Problem.

Here is the 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

ashwanigautam's gravatar image

accept rate: 0%

edited 25 Oct '16, 12:19

It can be solved using matrix exponentiation if you take log. Then define new sequence which is:


Then the question is reduced to standard recurrence solving where the matrix first row is :[k,k] instead of [1,1].


answered 24 Oct '16, 18:17

ankesh18's gravatar image

accept rate: 7%

edited 24 Oct '16, 18:21

wow!! beautiful solution.. doubt. the column vector then becomes [log(f(n-1)), log(f(n-2))]. So, don't you think taking log will include float number in the calculation and then finally when we will take anti log answer might be off some digits ?

(24 Oct '16, 18:44) ashwanigautam3★


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

ankesh18's gravatar image

accept rate: 7%

hey!! i understood what you said. here is my solution 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) ashwanigautam3★

in matrix multiplication, replace %mod by %(mod-1) and get AC!

(24 Oct '16, 21:16) ankesh186★

and the reason is ? stil not getting AC, care to try ?

(24 Oct '16, 21:19) ashwanigautam3★

link not working!

(24 Oct '16, 23:19) ankesh186★

try this , 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) ashwanigautam3★

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) ankesh186★

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 co-prime, so how can we say a matrix is co-prime to a number ? links are welcome too. :)

(25 Oct '16, 15:37) ashwanigautam3★

i dont know whether they hold for matrices!

(25 Oct '16, 18:08) ankesh186★
showing 5 of 8 show all
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 24 Oct '16, 17:14

question was seen: 842 times

last updated: 25 Oct '16, 18:08