non-fibo

Seeing the fame received by the Fibonacci numbers, the other Natural Numbers were feeling jealous. Therefore, to give them their shot at glory Mr. Non-Fibo now wants you to tell him the N^th- Non Fibonacci Number.
Input:
First line contains T which is the number of test cases.
T lines follow each with an integer N. 

Output:
For each N output the Nth Non-Fibonacci number.

Constraints:

1 ≤ T ≤ 10^5
1≤ N ≤ 10^15

Scoring:

1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^5 : ( 30 pts )
1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^9 : ( 30 pts )
1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^15 : ( 40 pts )

SAMPLE INPUT
3
1
2
3

SAMPLE OUTPUT
4
6
7

Explanation

The first few Natural Numbers that are Fibonacci are : 1,2,3,5,8,13..
Thus the first few Natural Numbers that are not Fibonacci are 4,6,7,9,...

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions:
T = int(input())
A = []
x = 1
y = 2
A.append(x)
N = 10**20
while(y<=N):
	A.append(y)
	x,y = y,x+y
#print A
for _ in range(T):
	N = int(input())
	x = N
	for i in range(1,len(A)):
		x -= A[i]-A[i-1] - 1
		if(x<=0):
			x += A[i]-A[i-1] - 1
			print(A[i-1]+x)
			break


def fib(n):
	f=[[1,1],[1,0]]
	if n==0:
		return 0
	power(f,n-1)
	return f[0][0]
	
def power(f,n):
	if n==0 or n==1:
		return
	m=[[1,1],[1,0]]
	power(f,n/2)
	multiply(f,f)
	
	if n%2 !=0:
		multiply(f,m)

def multiply(f,m):
	x =  f[0][0]*m[0][0] + f[0][1]*m[1][0]
	y =  f[0][0]*m[0][1] + f[0][1]*m[1][1]
	z =  f[1][0]*m[0][0] + f[1][1]*m[1][0]
	w =  f[1][0]*m[0][1] + f[1][1]*m[1][1]
	f[0][0] = x
	f[0][1] = y
	f[1][0] = z
	f[1][1] = w
n=2
arr=[]
while True:    
	
	x= fib(n)
	arr.append(x)
	n=n+1
	if x>10**15:
		break
art=[0, 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110]
for _ in range(eval(input())):
	n=eval(input())
	count=0
	temp=0
	if n<101:
		print(art[n])
	else:
		for item in arr:
			if item<=n:
				count+=1
			if item>n:
				break
		new=n+count


		for i in range(n+1,new+1):
			if i in arr:
				new+=1
		print(new)


	

	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
fib = [1,1]
c = 10**15
def fill_fibo():
	l = 1
	while(fib[l]<c):
		fib.append(fib[l]+fib[l-1])
		l+=1
	return
	
fill_fibo()
fib.pop(0)
for _ in range(eval(input())):
	res = eval(input())
	for i in fib:
		if(i<=res):
			res+=1
		else:
			break
	print(res)


num = [(4,4),(6,7)]
non = [1,2]
tot = [1,3]
while(tot[-1]<=(10**15)):
	num +=[(num[-1][0]+num[-2][0]-1,num[-1][1]+num[-2][1]+1)]
	non += [non[-1]+non[-2]+1]
	tot+=[tot[-1]+non[-1]]
l = len(tot)
t = eval(input())
for i in range(t):
	n = eval(input())
	for j in range(0,l):
		if(tot[j]>=n):
			diff = tot[j]-n
			print(num[j][1]-diff)
			break


def fib():
	a=1
	b=2
	ans=[a,b]
	while a<100+10**15:
		ans.append(a+b)
		a,b=b,a+b
		
	return ans

fibs=fib()

t=eval(input())
while t:
	t-=1
	n=eval(input())
	ans=n
	i=0
	while i<len(fibs):
		if (fibs[i]<=ans):
			ans+=1
		else:
			break
		i+=1
	print(ans)


for i in range(eval(input())):
	a,b,c = 1,2,3
	size  = eval(input())
	while size >0:
		a,b = b,c
		c = a+b
		size -= c-b-1
	size += c-b-1 # adding the redundant subtraction
	print(b + size)


def non_fibo(n):
	a=0
	b=1
	c=2
	while n>0:
		
		a=b
		b=c
		c=a+b
		n=n-(c-b-1)
	n=n+(c-b-1)
	return b+n
t=int(eval(input()))
for i in range(t):
	p=int(eval(input()))
	print(non_fibo(p))


for _ in range(eval(input())):
	x=1
	y=1
	z=eval(input())
	c=0
	while z>=x:
		t=x
		x=x+y
		y=t
		c+=1
	j=x-z
	if z==1 or z==2 or z==4:
		print(c+2+z)
	elif j<=c:
		print(c+1+z)
	else:
		print(c+z)