Помогите решить задачу пожалуйста c++

Question

Дано натуральное число, нужно его представить как произведение числе Фибоначчи больших 1. Вывести количество возможных вариантов разложения

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin >> n;

    for (long long i = 2; i * i <= n; ++i){
        while (n % i == 0){
            n /= i;
            cout << i << " ";
        }
    }

    if (n > 1)
        cout << n;
}

Answer 1

Моё решение:

#include <iostream>
#include <vector>

std::vector<int> fibonacci_decomposition(int num) {
    std::vector<int> fibonacci_numbers = {1, 1};
    std::vector<int> result;
    while (fibonacci_numbers.back() <= num) {
        int next_fibonacci = fibonacci_numbers[fibonacci_numbers.size() - 1] + fibonacci_numbers[fibonacci_numbers.size() - 2];
        fibonacci_numbers.push_back(next_fibonacci);
    }
    for (int i = fibonacci_numbers.size() - 2; i >= 1; i--) {
        while (num >= fibonacci_numbers[i]) {
            num -= fibonacci_numbers[i];
            result.push_back(fibonacci_numbers[i]);
        }
    }
    return result;
}

int main() {
    int num = 15;
    std::vector<int> fibonacci_decomposition_result = fibonacci_decomposition(num);
    std::cout << "Number of possible decompositions: " << fibonacci_decomposition_result.size() << std::endl;
    std::cout << "Decomposition: { ";
    for (int i = 0; i < fibonacci_decomposition_result.size(); i++) {
        std::cout << fibonacci_decomposition_result[i] << " ";
    }
    std::cout << "}" << std::endl;
    return 0;
}

На выходе будет:

Number of possible decompositions: 3
Decomposition: { 8 5 2 }

Здесь нат. число 15 разлагается на сумму 8, 5 и 2, которые являются числами Фибоначчи > 1

Answer 2

Негде проверить, но посмотрите, не годится это решение? Для чисел до порядка 1Е18.

#include <vector>
#include <iostream>

using namespace std;

vector<long long> F = {2, 3};

long long countF(long long n, long long min = 0) {
    if (n == 1) return 1;

    if (min == F.size()) return 0;

    for (long long i = min; i < F.size(); ++i) {
        if (n % F[i] == 0) {
            return countF(n / F[i], i) + countF(n, i + 1);
            }
        }

    return 0;
    }


int main() {
    for (long long a = 2, b = 3; a < 2000000000000000000ll;) {
        long long c = a + b;
        F.push_back(c);
        a = b;
        b = c;
        }

    long long N;
    cin >> N;
    cout << countF(N);
    }

Для простых примеров, кажется, работает.

БЛОГ НА HUSL

Помогите решить задачу пожалуйста c++

Ответы (2 шт):