I am trying to solve a problem which is described below,
Given value of f(0) and k , which are integers.
I need to find value of f( T ). where T<=10^10 (10 power 10)
Recursive function is,
f(n) = 2*f(n-1) , if 4*f(n-1) <=k
k - ( 2*f(n-1) ) , if 4*f(n-1) > k
If i solve by brute force then it will give me TLE. The code will run 10^10(10 power 10) time in worst case that gives me Time Limit Exceed. I need more efficient solution for this problem. Please help me. I don't know the correct algorithm.
Auto comment: topic has been updated by rpthegreat (previous revision, new revision, compare).
Auto comment: topic has been updated by rpthegreat (previous revision, new revision, compare).
What are the constrainsts of k and f0?
f0 <= 10 power 9
k <= 2*(10 power 9)
If k = 1 and f(0) = 109, the answer is very large. Do you need to find it modulo a prime? If not, you probably missed some inequality, like 2f(0) ≤ k.
Sir , If 4*(f(n-1) >k ) then f(n)= k-(2*f(n-1) ) sorry for typing mistakes
yes 2f(0)<=k
In this case all f(n) are between 0 and k / 2.
. 
.
You need to use fast exponentiation to find
. Use the inequality 0 ≤ f(n) ≤ k / 2 to find the sign ( ± ).
You are great , Sir
Why don't you give link to the problem?
I have not problem link because it is assigned by my senior friend. so problem is on my notebook. But if you have doubt regarding problem statement then please comment below.
u can print a value table in ur own computer,about every 100000 print one f(i),then u only need to calculate 100000 times in worst case.(u can adjust the interval 2 satisfy the limit of problem)