Fibonacci Sequence

Problem #67

Tags: arithmetic data-structures long-numbers classical

Who solved this?

Back to English version

Даже начинающие программисты обычно знакомы с Последовательностью Фиббоначчи которая задаётся так:

Таким образом получается:

0: 0
1: 1
2: 1 = 0 + 1
3: 2 = 1 + 1
4: 3 = 1 + 2
5: 5 = 2 + 3
6: 8 = 3 + 5

и так далее, так что если вы продолжите вычисления самостоятельно, то получите начало последовательности вроде:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Легко заметить что значения растут весьма быстро! 17-е уже больше тысячи, а 31-е превышает миллион...

Задача

Даны несколько чисел Фиббоначчи. Требуется найти их номер в последовательности Фиббоначчи.

Входные данные в первой строке указано количество чисел Фиббоначчи которые нужно обработать.
Остальные строки содержат по одному числоу Фиббоначчи каждая (из первой тысячи таких чисел).
Ответ должен содержать индексы (номера в последовательности) этих чисел, разделенные пробелами.

Пример:

входные данные:
5
610
34
0
1346269
10946

ответ:
15 9 0 31 21

Внимание: значения могут содержать более сотни цифр!

You need to login to get test data and submit solution.