Задача №115207. Произведение Фибоначчи
Напомним, что последовательность чисел Фибоначчи определяется следующим образом: \(F_0 = 1\), \(F_1 = 1\), \(F_n = F_{n-2} + F_{n-1}\). Последовательность чисел Фибоначчи начинается так: \(1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\).
Дано натуральное число \(n\). Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше 1.
Первая строка ввода содержит целое число \(t\) — количество тестов (\(1 \le t \le 50\))
Следующие \(t\) строк содержат тесты, каждая строка содержит одно целое число \(n\) (\(2 \le n \le 10^{18}\)).
Для каждого теста вывести одно число — искомое количество способов.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | \(2 \le n \le 100\) | первая ошибка | |
| 2 | 17 | \(2 \le n \le 10^5\) | 1 | первая ошибка |
| 3 | 9 | \(n = 2^k\) для некоторого \(k\) | первая ошибка | |
| 4 | 38 | \(2 \le n \le 10^9\) | 1, 2 | первая ошибка |
| 5 | 21 | \(2 \le n \le 10^{18}\) | 1–4 | первая ошибка |
В примере:
- число 2 можно представить в виде произведения чисел Фибоначчи единственным способом \(2=2\);
- число 7 нельзя представить в виде произведения чисел Фибоначчи;
- число 8 можно представить двумя способами: \(8 = 2\cdot 2\cdot 2\) и \(8 = 8\);
- число 40 можно представить двумя способами: \(40 = 2\cdot 2 \cdot 2 \cdot 5\) и \(40 = 5\cdot 8\).
5 2 7 8 40 64
1 0 2 2 3