Как найти все способы представить число в виде произведения чисел Фибоначчи?

Question

[impelix]

МОИ ИДЕИ
1) Ищем ряд чисел Фибоначчи до числа, Которое мы хотим представить как произведение (включая его)
2) Рекурсивно перебираем все варианты?
Может есть какой то другой более быстрый способ?
Задача на АСМП(https://acmp.ru/asp/do/index.asp?main=task&id_cour..., она же 2 задача регионального этапа всош в этом году

Comments

[mayton2019]

Как ты представишь число 11 ?

[Alexandroppolus]

mayton2019, там требуется количество способов. Для 11 будет 0 способов

[mayton2019]

Alexandroppolus, это - грустно дружище.

[Lynn «Кофеман»]

Чисел Фибоначчи до 10**18 меньше сотни. Можно в лоб перебором делать.

Answer 1

[Wataru]

Я бы рекурсивно решал, перебирая все числа фиббоначи. Если делится - запускаемся рекурсивно от частного. Суммируем ответы для всех вариантов делителя.

Что бы не перебирать разные перестановки множителей (а они в ответе, судя по примерам, не нужны), я бы передавал в функцию еще и максимальное разрешенное число фиббоначи. Изначально разрешены все числа, но при делении на какое-то число его же и передаем дальше. Таким образом функция будет перебирать только не возрастающие последовательности делителей.

Можно будет чуть ускорить, используя какой-нибудь ассоциативный массив для запоминания ответов. Его можно даже переиспользовать среди всех тестов.

Comments

[Alexandroppolus]

Если делится - запускаемся рекурсивно от частного.

можно сразу собрать все числа Фибоначчи, на которые делится число, и далее работать уже с этим массивом

[Wataru]

Alexandroppolus, Вообще, да. Но я думаю оно не особо на что-то повлияет. Там что делителей числа O(log), что чисел фиббоначи до него - логарифм. Ну, будет не log^2, а log^2/10 - не велика разница.

[Alexandroppolus]

Wataru, согласен, разница небольшая.

Вообще я думал, что в этой задаче будут какие-то хитрые оптимизации, связанные именно с числами Фиб., но по факту вместо них можно любую подобную последовательность воткнуть. Набросал ваш рекурсивный вариант на js, работает мгновенно..

[Wataru]

Alexandroppolus,
Да, любая экспоненциально растущая последовательность тут будет мнговенно работать, ибо потенциальных делителей мало.

[dollar]

фибоначчи