Напомним, что последовательность чисел Фибоначчи определяется следующим образом:
F0 = 1, F1 = 1, Fn = Fn−2 + Fn−1.
Последовательность чисел Фибоначчи начинается так:
1, 1, 2, 3, 5, 8, 13, 21, 34, . . ..
Дано натуральное число n. Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше 1.
Формат входных данных
Первая строка ввода содержит целое число t — количество тестов (1 <= t <= 50)
Следующие t строк содержат тесты, каждая строка содержит одно целое число n (2 <= n <= 10^18).
Формат выходных данных
Для каждого теста вывести одно число — искомое количество способов.
1 Ответ
Сделаем несколько ключевых наблюдений. Во-первых, числа Фибоначчи растут с экспоненциальной скоростью. Существует лишь 85 чисел Фибоначчи, больших 1 и не превышающих 10^18. Во-вторых, числа Фибоначчи имеют достаточно мало общих делителей. На самом деле можно доказать, что если нумеровать числа Фибоначчи с 1 (F1 = 1, F2 = 1, F3 = 2, . . .), то НОД(Fa, Fb) = FНОД(a,b).
lo ng lo ng bt ( lo ng lo ng n , i n t p ) {
i f ( n == 1 ) r e t u r n 1 ;
i f ( p >= f i b . s i z e ( ) ) r e t u r n 0 ;
i f ( n < f i b [ p ] ) r e t u r n 0 ;
lo ng lo ng r e s = bt ( n , p + 1 ) ;
i f ( n % f i b [ p ] == 0 ) {
r e s += bt ( n / f i b [ p ] , p ) ;
}
r e t u r n r e s ;
}