POWFIB - Fibo and non fibo
The problem is simple.
Find (a^b) % MOD
a = Nth non-fibonacci number
b = (Nth fibonacci number)%MOD
MOD = 10^9+7
Consider fibonacci series as 1,1,2,3,....
Note : It is guaranteed that Nth non-fibonacci number will always be less than MOD value for every value of N used.
First line contains T , the number of test cases.
Each next T lines contains a number N.
Print T lines of output where each line corresponds to the required answer.
Announcement: Constraints are updated. Sorry for inconvenience occurred.
3 3 2 1
49 6 4
For N=3 : 3rd non fibo number =7, 3rd fibo number=2. ans= (7^2) %MOD =49
For N=2 : 2nd non fibo number =6, 2nd fibo number=1. ans=(6^1) %MOD=6
For N=1 : 1st non fibo number =4, 1st fibo number=1. ans= (4^1) %MOD =4
Note: Test cases have been updated and costraints are changed. Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.
@nimphy is correct I think.... "b" should be calculated under modulo (MOD-1) and not MOD.
when I get “b”，I should mod 1e9+7-1，right？ But I get WA； while mod 1e9+7 get AC。What is the problem~~~~
Wrong answer on test case 14 but why!!
I have got 3 WAs. I am sure my code is correct. :/
O(T*log(n)) gives TLE with scanf/printf. Too tight Time Limit?
@ivar.raknahs : can you please check my latest submission .Last edit: 2016-06-05 16:53:07
using matrix exponantion....AC in one go.
learnt a lot
finally solved with lowest time in java after more than 25 tle and wrong answer :)