A function is defined as follows : GF(A,B,0)=A GF(A,B,1)=B GF(A,B,N)= GF(A,B,N1)+GF(A,B,N2) where N>1 Given 3 non negative numbers A B N returns remainder from division by 1000000007 For example given A =3 B=4 n =5 the function should return 29 BECAUSE GF(3,4,0)= 3 mod 1000000007 = 3 GF(3,4,1)= 4 mod 1000000007 = 4 GF(3,4,2)= (GF(3,4,0)+GF(3,4,1)) mod 1000000007 =7 GF(3,4,3)= (GF(3,4,1)+GF(3,4,2)) mod 1000000007 =11 GF(3,4,4)= (GF(3,4,2)+GF(3,4,3)) mod 1000000007 =18 GF(3,4,5)= (GF(3,4,3)+GF(3,4,4)) mod 1000000007 =29 Can anyone solve this question in time complexity: O(logN) space complexity: O(1) asked 09 Sep '16, 01:12

For finding the nth fibonacci number, you can use matrix exponentiation. See code at https://ronzii.wordpress.com/2011/07/09/usingmatrixexponentiationtocalculatednthfibonaccinumber/ answered 10 Sep '16, 02:32
Can you please code it I am facing issue with overflow. or this is my code http://ideone.com/mmGyDZ if you can fix integer overflow in it. This code is not able to calculate it for big numbers. It would be a great help.
(10 Sep '16, 07:37)

For getting a very fast implementation of only fibonacci numbers, you can refer to this thread : https://discuss.codechef.com/questions/62693/fastestwaytocalculatenthfibonaccinumbermodulom BTW, I have a even smaller implementation for fibonacci numbers and according to the FIB64 problem on Spoj, I was ranked 14 among some of the fastest solution. You can find my implementation at https://github.com/likecs/CompetitiveCoding/blob/master/C%2B%2B/Maths/fibonacci_mod_m.cpp It works for all types on input and also handles the case even if we are multiplying even 2 "long long " values as well. The complexity is O(logn) and space complexity is O(1). Also, since mod operations are costly, the code has been designed in such a way so as to carry out mod operations only when required. Hope it helps now. answered 11 Sep '16, 15:32
@likecs Thanks. Can you help me with this,
(11 Sep '16, 19:06)
I think the question is already answered by @spinovations.
(12 Sep '16, 13:49)
Can you explain what does mulmod function do?
(13 Sep '16, 00:04)
You can refer to this http://codeforces.com/blog/entry/15884
(13 Sep '16, 15:20)

If we observe the given function, we can see a pattern All that is left is to evaluate the expression properly modulo 10^{9}+7. Hope this helps :) answered 09 Sep '16, 03:06
can you provide source code.
(09 Sep '16, 23:06)
@meooow @likecs @spinovations @slimtashady This is my code http://ideone.com/mmGyDZ if you can fix integer overflow in it. This code is not able to calculate it for too big values. It would be a great help.
(10 Sep '16, 07:37)
@saksham458
You are facing overflow because of lines such as these It overflows when you do ((int)*(int)), so taking modulo of the wrong result does not help. You need to do this
(10 Sep '16, 18:02)
why do we need to cast values to long?
(10 Sep '16, 18:25)
@meooow is there any technique for further optimazation. It's taking too log for the inputs A=2147483647 A=2147483647 N=1000000000
(10 Sep '16, 18:26)
@saksham458
(11 Sep '16, 23:29)
showing 5 of 6
show all
